I know a few graph invariants and it seemed that these two graphs do not have the same amount of circuit length $3$.
(our definition of a circuit is a closed path, a path being a walk with no repeated edges)

enter image description here

In particular, it seems that $G_1$ has $9$ circuits of length $3$ in the anti-clockwise direction (so there are $18$ circuits of length $3$ in total).

$G_2$ has only $6$ circuits of length $3$ in the anti-clockwise direction so it has $12$ circuits in total of length $3$.

So $G_1$ is not isomorphic to $G_2$, however, my solutions say that they are.

  • 1
    $\begingroup$ Where do you find $6$ or $9$ circuits of length $3$ in either? I found only two in $G_1$ ($a,c,d$ and $c,d,e$) and two in $G_2$ ($x,y,z$ and $x,y,t$). $\endgroup$ – Misha Lavrov Oct 23 '17 at 1:02
  • $\begingroup$ The one I'm looking at for $G_1$. $adca,dcad,cadc$ (so $3$ for that triangle) $cdec,decd,ecde$ (so $3$ for that triangle) Actually, I jsut found my mistake in the counting of $G_1$ after writing that, thanks! $\endgroup$ – Natash1 Oct 23 '17 at 1:06

Actually these graphs are isomorphic. If you take f(a)=z f(b)=u f(e)=t f(d)=x f(c)=y f is an isomorphism because if ab is an edge in G1, f(a)f(b) is an edge in G2


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.