# Are these two 10-vertex graphs isomorphic?

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.

-
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 '13 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 '13 at 17:07
Have Powerpoint? Just create one graph with points and lines and move them around till they look like the other graph – Dario Feb 3 '13 at 17:15
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 '13 at 17:34

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.

-
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 '13 at 20:36

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.

-
is that a valid reason for two graphs to not be isomorphic? – thebottle394 Feb 3 '13 at 17:59

For Isomorphism four conditions should be true: 1. Both the graphs should have the same number of vertices. 2. Both the graphs should have the same number of edges. 3. Both the graphs should have the same number of vertices of some degree. 4. Adjacency should always be maintained.

In both the graphs the first three conditions which I mentioned are true. But if you check the fourth condition and carefully notice you will see that adjacency has not been maintained. All the vertices are of degree 3 agreed but if i start mapping suppose I map a to 1. Then since b,j and f are adjacent so I try mapping b,j and f to the nodes which are adjacent to 1 i.e. 2,7 and 10. If I map b to 2 then I am allowed to only map j to either 7 or 10 to preserve adjacency. But mapping j to either of 7 or 10 doesn't preserve adjacency since in the first graph b and j are adjacent whereas none of 2,7 or 10 are adjacent.

So, the graphs are non-isomorphic since you cant find a mapping or a bijection function

-