Graph Isomorphism: Prove Only 1 Graph w/ Degree Seq (3,3,3,3,4)

  • Thread starter Thread starter Petkovsky
  • Start date Start date
  • Tags Tags
    Graph Isomorphism
Petkovsky
Messages
61
Reaction score
0
How many graphs(non isomorphic) can you construct from the degree sequence (3,3,3,3,4). The answer has to be proven of course.

The only one I could find was a W5 graph, but i can't prove that it is the only one. I know that for two graphs to be isomorphic, a bijection has to exist between the two vertex sets, however i don't know where to start from. Any help would be appreciated.
 
Physics news on Phys.org
Just try to construct it from the degrees and see that W5 is the only possibility.

Sketch:
Assume we have a graph with degree sequence (3,3,3,3,4).
- Let A be the vertex with degree 4. A is connected to all vertices.
- Let B be some other vertex than A. B has degree 3 and is therefore connected to all vertices but one which we can call C.
- C has degree 3 so is connected to all vertices but one, and since it isn't connected to B we know that it is connected to all but B.
- Let D be some vertex other than A,B,C. D is connected to A, B and C and has degree 3 so it's connected exactly to these.
- Let E be the last vertex. E is connected to A, B, C.

This is isomorphic to W5 which can be seen by sending A to the center of the wheel and sending (B,C,D,E) to the cycle.
 
Aha, i see now. Thank you.
 
Thread 'Use greedy vertex coloring algorithm to prove the upper bound of χ'
Hi! I am struggling with the exercise I mentioned under "Homework statement". The exercise is about a specific "greedy vertex coloring algorithm". One definition (which matches what my book uses) can be found here: https://people.cs.uchicago.edu/~laci/HANDOUTS/greedycoloring.pdf Here is also a screenshot of the relevant parts of the linked PDF, i.e. the def. of the algorithm: Sadly I don't have much to show as far as a solution attempt goes, as I am stuck on how to proceed. I thought...

Similar threads

Back
Top