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.

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