Of 3 graphs, which are isomorphic? Justify answer, providing bijection.

[Havie]

Hello Math forums,

I know the rules are to ask a specific question here, but I am afraid I am not able to make it quite far on this problem as the teacher barely covered it on our last day of class.



I understand an Isomorphic graph is when two graphs have similar properties in a way that some function can create a bijection to preserve adjacency,
Problem is i can't quite figure out how to do this,
the # of vertices are = and the deg sequence of all 3 graphs are the same.
No idea how to prove anything else though.

Would anyone mind taking the time to help me out?
Thanks

 

[Dr.Peterson]

Hello Math forums,

I know the rules are to ask a specific question here, but I am afraid I am not able to make it quite far on this problem as the teacher barely covered it on our last day of class.

View attachment 10710

I understand an Isomorphic graph is when two graphs have similar properties in a way that some function can create a bijection to preserve adjacency,
Problem is i can't quite figure out how to do this,
the # of vertices are = and the deg sequence of all 3 graphs are the same.
No idea how to prove anything else though.

Would anyone mind taking the time to help me out?
Thanks

The first step is just to try out a possible bijection and see if it works. You've labeled the vertices in G1; you might look at G2, starting from any one vertex, and, following the edges, label four vertices a, b, d, c. Then, if this is working, d should connect back to a, and you should be able to identify e, f, g, h as being adjacent to a, b, c, d. If that doesn't work, you might start somewhere else and try again; or you might have discovered something about G2 that makes it different from G3. (You might first want to relabel G1 so that the letters form a single loop, a, b, c, d, e, f, g, h, which may make the work easier.)

Then try the same thing with G3.

An alternative is to look at how vertices in G1 are connected; do you see that this graph is isomorphic to the edges of a cube? That is a very familiar graph, so you might be able to recognize some differences in G2 or G3.

Or, what I often do, just try moving vertices around to untangle G2 and G3 (removing crossings), so you can see better what they look like.

The main thing is just to try something. As you explore each graph in some way, you will be becoming more familiar with them, and should start to see which are isomorphic. But my first suggestion is how you will have to find the bijections, where possible.

 

[Havie]

thanks for your advice Dr. Peterson.
I guess brute forcing it is the only way for me to start then

 

[Dr.Peterson]

thanks for your advice Dr. Peterson.
I guess brute forcing it is the only way for me to start then

Not necessarily the only way, but easy enough that it may not be worth looking for another. To me, this is not brute force, so much as exploration.

The initial goal is just to get to know these graphs; you will probably find out quickly enough whether it's worth it to keep trying for a bijection (which you have to find anyway), or see a property that one has and another lacks (e.g. 4-cycles). And they are simple enough that it shouldn't take many tries to find the bijection if it exists. (Note that all vertices of each of them are equivalent, so it doesn't matter where you start.)