I have to prove or disprove that the following graph are isomorphic?

enter image description here

If I will give the following isomorphism,

\begin{align*} a & \mapsto 1\\ b & \mapsto 2\\ e & \mapsto 5\\ d & \mapsto 8 \end{align*} then we see that $h$ has only one uncommon vertex to $a$ which is $g$ but the vertex $8$ has two vertices which is not directly connected to the vertex $1$. Hence the two graphs are Not isomorphic.

Am I correct?

  • $\begingroup$ Suggestion: show that just one of the two graphs is bipartite. $\endgroup$ – Gerry Myerson Feb 6 '17 at 6:08

You have a few problems. First, you haven't given the full map between the vertex sets. Second, you've only argued that this map isn't an isomorphism. You haven't clearly ruled out the possibility that some other map is an isomorphism. I think you're trying to argue that the partial map you've shown is perfectly general, but you haven't started anything to that effect.

Typically, showing that two graphs are not isomorphic involves showing some invariant differs between them. Common invariants are degree sequence, diameter, connectivity, chromatic number, and Hamiltonicity.

As a hint, notice that every edge in the left graph is contained in two otherwise disjoint 4-cycles.

  • $\begingroup$ No I have taken an arbitrary map. Since, the first vertex can map to any vertex. Now using that I try to find the other possibilities but I got a contradiction. So, that is why I conclude that the graphs are not isomorphic. $\endgroup$ – Sachchidanand Prasad Feb 3 '17 at 7:41
  • $\begingroup$ This may be a problem of wording. You said, "If I will give the following isomorphism." That sounds like you're presenting an isomorphism. Even if you are making an argument about a general map, you must make that explicit. $\endgroup$ – mephistolotl Feb 3 '17 at 7:58
  • $\begingroup$ Yeah I got your point. $\endgroup$ – Sachchidanand Prasad Feb 3 '17 at 8:26

Another explanation of isomorphism is :
see that for any vertex, all other vertex distances need to be same.
We choice a vertex from left graph (see that all other vertices are equivalent) : a
Vertices which have distance 1 from a : b,d,e
Vertices which have distance 2 from a : c,f,h
Vertices which have distance 3 from a : g
Now let us see what happen with a vertex of right graph, vertex 1 :
Vertices which have distance 1 from 1 : 2,5,8
Vertices which have distance 2 from 1 : 3,4,6,7
Vertices which have distance 3 from 1 : no one
So, we found a invariant : "number of vertices which have a distance 3 from any vertex". For left graph this is 1 and for right graph this is 0
Indeed there are very similar but not isomorph :
right graph



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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