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

[Petkovsky]

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.

 

[rasmhop]

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.

 

[Petkovsky]

Aha, i see now. Thank you.