Proof verification: (Pretty pictures :) )Showing two graphs are not isomorphic. Bondy/Murty - Graph theory Page 5

323 Views Asked by At

I want to show the below two graphs are not isomorphic. Treat the left as graph $\bf G$ and the right as graph $\bf H$.

enter image description here

$\bf G$ and $\bf H$ are not isomorhpic: Although we have a bijective mapping between vertices, we do not have the same adjacent vertices in $\bf G$ as in $\bf H$, as although $B$ and $C$ are adjacent in $\bf H$, $F$ and $I$ are not adjacent in $\bf G$. Also $F$ and $H$ in $\bf G$ are adjacent, but $B$ and $D$ in $\bf H$ are not.

Question: Is the above all it takes as a proof of this, and have I mistaken any of the concepts?

Thank you.

1

There are 1 best solutions below

1
On BEST ANSWER

Showing two graphs are isomorphic/non-isomorphic involve showing that the two graphs are structurally the same/different. The names of the vertices are not structural properties so we have to take care that names are not the crucial part of the proof.

To show two graphs are non-isomorphic, we must consider all possible bijective mappings between the two sets of vertices and show that none of these mapping preserve the edge relations. Hence we cannot make any assumptions which vertices are mapped onto which unless we have a structural reason for it.

In your example, you mentioned $B$ and $C$ are adjacent in $\mathbf{H}$ but $F$ and $I$ are not adjacent in $\mathbf{G}$. However, it is possible that $B$ and $C$ are not mapped to $F$ and $I$ in a given bijective mapping so making this comparison will not be valid.

You are probably on the right track in identifying that those vertices are key to the fact that the two graphs are non-isomorphic. Hence, we want to identify unique structural properties to identify these vertices. For example, in both graphs $\mathbf{G}$ and $\mathbf{H}$, there is only one unique vertex that has a loop ($I$ and $C$ respectively). Hence any possible isomorphic mapping must map one to the other and vice versa.

In graph $\mathbf{H}$, this unique vertex (with a loop) is adjacent to a vertex of degree 4. In graph $\mathbf{G}$ however, this vertex does not have this property. Hence the two graphs are not isomorphism.