Proving Uniqueness of Graphs with a Given Degree Sequence

Click For Summary

Discussion Overview

The discussion revolves around the uniqueness of graphs with a given degree sequence, specifically the sequence s:7,6,5,4,4,3,2,1. Participants explore the concept of proving that there exists only one graph corresponding to this degree sequence and the implications of isomorphism in graph theory.

Discussion Character

  • Exploratory
  • Technical explanation
  • Debate/contested

Main Points Raised

  • One participant expresses uncertainty about proving the uniqueness of the graph with the specified degree sequence, suggesting that they need to show the graph is nonisomorphic.
  • Another participant proposes a method involving mapping nodes of the same degree to demonstrate isomorphism, starting with the highest degree node and working downwards.
  • A participant questions whether the graph is isomorphic, indicating a potential misunderstanding of the problem's requirements.
  • In response, a participant asserts that the graph is indeed nonisomorphic and suggests looking for contradictions in the algorithm to support this claim.
  • Another participant argues that once the higher degree nodes are determined, the remaining nodes can be connected in multiple ways, implying that the resulting graphs may be isomorphic.
  • A later reply critiques the terminology used in the discussion, emphasizing the need to specify what the graph is (non)isomorphic to and suggesting that all graphs with the given degree sequence may be isomorphic to each other.
  • One participant acknowledges confusion regarding isomorphic graphs and expresses gratitude for the assistance provided.

Areas of Agreement / Disagreement

Participants express differing views on whether the graph with the given degree sequence is unique or if multiple isomorphic graphs can exist. The discussion remains unresolved, with competing perspectives on the nature of isomorphism in this context.

Contextual Notes

There are indications of confusion regarding the terminology of isomorphic graphs and the conditions under which graphs can be considered nonisomorphic. The discussion highlights the complexity of formalizing concepts in graph theory.

philosophking
Messages
175
Reaction score
0
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! :)
 
Mathematics news on Phys.org
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
 
isn't the graph isomorphic?
 
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.
 
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.
 
neurocomp2003 said:
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.
 
Oh, you're right. I guess I'm just a little confused still on isomorphic graphs in general. Thanks for your help.
 

Similar threads

Undergrad What is a Clique in Graph Theory?
  • · Replies 14 ·
Replies
14
Views
3K
Graduate How Do You Prove Minimum Vertex Degree in Graph Theory?
  • · Replies 1 ·
Replies
1
Views
3K
Proving uniqueness of almost irregular graphs with equal degrees for n=2k
  • · Replies 3 ·
Replies
3
Views
3K
Graduate Concrete examples of randomness in math vs. probability theory
  • · Replies 11 ·
Replies
11
Views
3K
Proving a (known isomorphic) graph is isomorphic
  • · Replies 6 ·
Replies
6
Views
3K
Undergrad Proving Connectedness of Cycle Graphs: An Alternative Approach
  • · Replies 6 ·
Replies
6
Views
5K
Combinatorics/graph theory or number theory books
  • · Replies 1 ·
Replies
1
Views
4K
Undergrad Questions regarding Kurepa's Conjecture
  • · Replies 1 ·
Replies
1
Views
3K
Undergrad What are the definitions of graph theory and its components?
  • · Replies 2 ·
Replies
2
Views
4K
Graduate Does G with all its degrees at least three contain a cycle with a chord?
  • · Replies 3 ·
Replies
3
Views
4K