Is there a simpler way to prove these graphs are non-isomorphic

graph theorygraph-isomorphism

The graphs

enter image description here

My solution

Graphs $\mathcal{G}$ and $\mathcal{H}$ have the same number of edges, vertices and the same degree sequence. They also have the same number of 3-cycles.

I proved they are not isomorphic by counting the 4-cycles in each graph but this was very tedious.

Graph $\mathcal{G}$ has eight 4-cycles, namely, (ABCDA), (ABCEA), (AGCDA), (AGCEA), (ABGFA), (CDEHC), (ADCEA), (BAGCB). While graph $\mathcal{H}$ has ten 4-cycles, namely, (57265), (58765), (32673), (57345), (43784), (45784), (23412), (12651), (12751), (14851).

Question

Is there any quicker way to show these graphs are isomorphic than what I did?

Best Answer

$\mathcal H$ has an edge between the two vertices of degree $5$, whereas $\mathcal G$ does not.

Related Question