1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Graph isomorphism

  1. Jan 22, 2010 #1
    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.
  2. jcsd
  3. Jan 22, 2010 #2
    Just try to construct it from the degrees and see that W5 is the only possibility.

    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.
  4. Jan 22, 2010 #3
    Aha, i see now. Thank you.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook