Proving Uniqueness of Graphs with a Given Degree Sequence

[philosophking]

Hey everyone,

I wasn't sure where to put this, since graph theory doesn't really have it's own name here (we don't even have a combinatorics or discrete math category...), so I decided to just put it here in "General Math". My question pertains to degree sequences of graphs.

I'm asked to show that s:7,6,5,4,4,3,2,1 is graphical. An algorithm for this is derived from a theorem in my book (Chartrand and Lesniak's book, 4th ed.). I can do this no problem.

But then I am asked to prove that there exists only one graph with this degree sequence, and I'm not sure how to do this. Basically, I have to show that the graph is nonisomorphic, I think.

This is for an independent study of graph theory, and any help would be greatly appreciated! :)

 

[snoble]

It seems pretty straight forward conceptually but (as always with graph theory) it seems like it is a pain to formallize. The hypothesis you want to show is that if you take to two graphs with that degree sequence and take a map f that maps nodes of the same degree to each other (for the nodes of degree 4 they can be mapped to either node in the second graph of degree 4) then f is an isomorphism. Start with the nodes of degree 7. Show that the node of degree 7 is has an edge in common with every other node in both graphs. Then go down the list.

There is a classic word problem about couples shaking hands at a party that is similar to this problem.

Hope that's some help
Steven

 

[neurocomp2003]

isn't the graph isomorphic?

 

[philosophking]

That's our question, but my book asks me to prove that it isn't, so I'm guessing that it is nonisomorphic.

Yes, snoble, that did help me. I'm going to consider your algorithm and try to find some sort of contradiction in there to show that it is nonisomorphic. If anyone could help with going a little more forward with helping me actually solve the problem, that would be great.

Thank you again for your help.

 

[neurocomp2003]

but it is...do the following as snoble suggested start with the arbitrary 7 node...then move to a 6 node...the 6 node will give away another node...same with the 5 node...
then your left with three nodes degree 4 ,4,3 ...you can attach them anyway you want.

 

[shmoe]

then your left with three nodes degree 4 ,4,3 ...you can attach them anyway you want.

Once you've determined the degree 7,6 and 5 nodes, you'll have 3 choices for the 3 node. All will produce the same (isomorphic) graph.

There's some strange usage of terminology present in this thread. Phrases like "the graph is (non)isomorphic" are meaningless as far as I know, you have to indicate what it's (non)isomorphic to. So this question asks you to show that 7,6,5,4,4,3,2,1 is graphical (meaning such a graph exists) and all such graphs with this degree sequence are isomorphic to each other.

 

[philosophking]

Oh, you're right. I guess I'm just a little confused still on isomorphic graphs in general. Thanks for your help.