Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Isomorphisms of graphs

  1. Sep 6, 2010 #1

    I didn't know where graph theory falls into, so I decided to post this question on here; please let me know if there is another thread where this post is more appropriate.

    I am working on The Princeton Review's "Cracking the GRE Math Subject Test", and there was one problem about graph theory that I am puzzled about, and I was wondering if anyone can answer my question.

    The question is the following:

    Which of the following graphs are isomorphic?

    Graph I:

    Vertices are placed like:


    and edges are: AB, BC, and CD

    Graph II:

    Vertices are placed like


    and edges are: EG, GF, FH

    Graph III:


    (so edges are JK, KL, LM)

    Sorry for a poor description of those graphs, but that's the best I could do. I thought all three of them were isomorphic, but the solution in the book says graphs I and II are not isomorphic by the following reason:

    "Graph I has four vertices with the following edges: AB, BC, CD. Although there exists a bijective function f such that f(A) = E, f(B) = F, f(C) = G, and f(D) = H, adjacencies are not preserved; for example, there is no edge EF."

    I'm quite confused about this argument because I thought f(A) = E, f(B) = G, f(C) = F, and f(D) = H is a bijective map that preserves adjacencies, and therefore I and II are isomorphic, but the solution in the book doesn't see this way.

    If you know what is wrong, please let me know; it is possible that I'm not understanding the concept of isomorphisms of graphs.


  2. jcsd
  3. Sep 6, 2010 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    The three graphs you wrote are isomorphic. (Are you sure they are the three graphs of the problem?)
  4. Sep 6, 2010 #3
    Yes, they are the graphs that are given on the problem (maybe I should post an actual picture if I have time). And I believe those three graphs are isomorphic too.

    The problem set on this chapter (7. Additional Topics) is full of errors--they asked me to find a harmonic conjugate of a function that is not even harmonic, and they also asked me to find the probability of getting between 40 to 50 "heads" by flipping a fair coin 10 times (and 0% was not one of the answers). It would be nice if those errors are obvious, but some of them weren't very obvious.
  5. Sep 9, 2010 #4
    I'm very curious. You wouldn't care to identify the textbook, would you (author,title, publisher, year of publication)? Where are you studying? Were you required to buy this "textbook"?

    You don't need to answer of course, but since I'm interested in math education, this is something I'd like to look into.

    You can send me a private message by clicking on my username.
    Last edited: Sep 9, 2010
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook