Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 5 down vote favorite

Two graphs

Explain if these two graphs are isomorphic. If so, give the 1-1 correspondence of nodes.

I've checked that the two graphs have the same degrees, edges, and vertices, and check that they both aren't bipartite. I just can't seem to come up with a correct 1-1 node correspondence.

share|improve this question
1  
Just try! Finding out whether two graphs are isomorphic is actually a quite hard problem, so hard that we can use in cryptography. However, one hint is that isomorphisms cannot change the degree of nodes, so if the graphs aren't isomorphic, you might find this out by counting how many nodes are there of degree 1, 2, $\ldots$. – Dario Feb 3 at 17:05
I've checked that the two graphs have the same degrees,edges, and vertices, and check that they both aren't bipartite. I just can't seem to come up with a correct 1-1 node correspondence. – thebottle394 Feb 3 at 17:07
2  
Have Powerpoint? Just create one graph with points and lines and move them around till they look like the other graph – Dario Feb 3 at 17:15
1  
I downvoted this question for lack of effort; then saw your comment. I added it to your question so I can change my vote to a +1. – Douglas S. Stones Feb 3 at 17:34

2 Answers

up vote 4 down vote

The graph at left has a 3-cycle $(a,b,j)$ (also $(f,e,g)$). The graph at right has none. They are not isomorphic.

It may be worth noting that the graph at right is simply (the skeleton of) a pentagonal prism; consequently, each vertex is (in an appropriate sense) "equivalent" to every other vertex. This is not the case in the graph at left.

Also, the graph at right, as illustrated, is planar; no edges intersect. In the graph at left, you can replace "chords" $bj$ and $eg$ with paths that travel "outside the circle", eliminating intersections with $af$, but you can't do that with both of $ch$ and $di$ and not have $ch$ and $di$ cross; an edge intersection is inevitable (although this needs rigorous proof), so the graph is non-planar.

share|improve this answer
1  
The outer cycle together with the three chords $af$, $ch$, $di$ give a subdivision of $K_{3,3}$, so the graph on the left is not planar. – Chris Godsil Feb 3 at 20:36
up vote 1 down vote

The right one has four 4-cycles: 1,2,3,10; 3,4,9,10; 4,5,8,9; 5,6,7,8. I can't find more than c,d,i,h on the left. The one on the right has two disjoint 5-cycles: 1,7,8,9,10; 2,3,4,5,6. On the right I can find more 5-cycles, but none involve a or f. Maybe I'm overlooking some.

Added: Yes, this is a route to show they are not isomorphic. For them to be isomorphic you need the adjacency matrix to be the same once you find the proper mapping. If you can find any property that doesn't match they are not isomorphic. The degrees, number of vertices, number of edges are easy to check, so should be the first step. To make sure, you would say that whatever 3 maps to has to be part of two four-cycles, which also include the thing 10 maps to. Look through all the vertices and see that you can't satisfy this.

share|improve this answer
is that a valid reason for two graphs to not be isomorphic? – thebottle394 Feb 3 at 17:59

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.