Are the following graph isomorphic?

Question

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

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?

Answer 1

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.

Answer 2

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 :

Daniel

Answer 3

The given graphs are Not isomorphic.

Let me call the left graph as $G$ and right graph as $H$.

We can see that graph $G$ has no odd length cycle, so $G$ is bipartite graph (actually $G$ is a hypercube graph $Q_3$).

Graph $H$ has cycles of length $5$ (for example, take $1-2-3-4-5-1$), So, H is Not bipartite graph.

So, $G$ and $H$ are Not isomorphic.