Graph Isomorphisms: Understanding the Concept and Breaking Down Examples

  • Context: Undergrad 
  • Thread starter Thread starter PieceOfPi
  • Start date Start date
  • Tags Tags
    Graphs
Join the discussion
Registration is free. Ask a follow-up in this thread, or start your own.
Sign up Log in
3 replies · 3K views
PieceOfPi
Messages
185
Reaction score
0
Hi,

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:

BC
AD

and edges are: AB, BC, and CD

Graph II:

Vertices are placed like

FG
EH

and edges are: EG, GF, FH

Graph III:

J---K---L---M

(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.

Thanks!

PP
 
Physics news on Phys.org
Hurkyl said:
The three graphs you wrote are isomorphic. (Are you sure they are the three graphs of the problem?)

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.
 
PieceOfPi said:
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.

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: