[Math] Is the number of simple circuits of a particular length preserved in two isomorphic graphs

discrete mathematicsgraph theorygraph-isomorphism

If two graphs are isomorphic, and one has a simple circuit of a particular length, must the other graph also have a circuit of the same length?

Do they also have to have the same number of such circuits?

In the book that I use it is claimed that the following two graphs are isomorphic:

enter image description here

Graph G has two circuits of length 5, but no circuits of length 4. Graph H has one circuit of length 5 and one circuit of length 4. Doesn't this mean that they are not isomorphic?

Edit: The book shows their isomorphism with the function f, where f(u1)=v6, f(u2)=v3, f(u3)=v4, f(u4)=v5, f(u5)=v1, f(u6)=v2. Doesn't this prove that they are isomorphic?

Best Answer

Yes, it does mean that they’re not isomorphic. If they were isomorphic, an isomorphism $h:V(H)\to V(G)$ would carry the $4$-cycle with vertices $v_3,v_4,v_5$, and $v_6$ to a $4$-cycle in $G$. Since $G$ has no $4$-cycle, no such isomorphism can exist.

Related Question