Graph Isomorphisms: Understanding the Concept and Breaking Down Examples

[PieceOfPi]

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

 

[Hurkyl]

The three graphs you wrote are isomorphic. (Are you sure they are the three graphs of the problem?)

 

[PieceOfPi]

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.

 

[SW VandeCarr]

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.

 

[blue_raver22]

Hello,

Thank you for your question about graph isomorphisms. Graph theory is a branch of mathematics that deals with the study of graphs, which are mathematical structures that represent relationships between objects. Isomorphism in graph theory is a concept that describes the structural similarity between two graphs. Two graphs are considered isomorphic if there is a bijective function between their vertices that preserves the relationships between their edges.

In the problem you mentioned, it seems that you have correctly identified that graphs I and II are isomorphic because there is a bijective function that preserves adjacencies between their vertices. However, the solution in the book is also correct in pointing out that the specific function you suggested, f(A) = E, f(B) = G, f(C) = F, and f(D) = H, does not preserve the edges between the vertices. In graph theory, it is important to consider both the vertices and edges in determining isomorphism.

To better understand this concept, let's look at an example. Imagine you have two graphs, graph A and graph B, with the following structures:

Graph A:

Vertices: 1, 2, 3
Edges: 12, 23, 31

Graph B:

Vertices: A, B, C
Edges: AB, BC, CA

If we try to map the vertices of graph A to those of graph B, we could say A = 1, B = 2, and C = 3. However, this mapping does not preserve the edges between the vertices, as 12 in graph A corresponds to AB in graph B, which is not one of the given edges. Therefore, even though the vertices can be mapped bijectively, the edges are not preserved, and these two graphs are not isomorphic.

In summary, isomorphism in graph theory is a concept that considers both the vertices and edges in determining structural similarity between two graphs. I hope this helps clarify the concept for you. Good luck with your studies!

Best,