Cycles of given length preserved under graph isomorphism

Question

Is it true that if $(G,E)$ and $(G', E')$ are two finite simple graphs, then they cannot be isomorphic if all vertices in $G$ are in a 4-cycle, whereas a vertex in $G'$ is not?

I have a feeling the answer is yes. I'm not sure how to show this though. One way may be to consider the powers of the similar adjacency matrices, $A_G$ and $A_{G'}$. We would have that $A_G^4$ has nonzero diagonal entries whereas $A_{G'}^4$ has a diagonal entry which is $0$. And the powers of these two matrices must still be similar. Moreover $A^4_G$ and $A^4_{G'}$ are symmetric matrices. I'm not sure where to go from here though.

A more general question would be whether corresponding vertices of isomorphic graphs are attached to the same number of $k$-cycles. So we would be considering diagonal entries of $A_G^k$.

Answer 1

Let $(G,E)$ be a graph in which every vertex is a member of a $4$-cycle and let $f:(G,E) \rightarrow (G',E')$ be a graph isomorphism. Suppose (for the purposes of contradiction) that $a'$ is a vertex in $(G',E')$ that is not in a $4$-cycle. By the definition of graph isomorphism, there is an $a \in (G,E)$ such that $f(a) = a'$. Let $a-b-c-d-a$ be any of the $4$-cycles in $(G,E)$ containing $a$. Then the edge $a-b$ is taken to the edge $f(a)-f(b)$ in $(G',E')$ by $f$. Similarly, the edges $f(b)-f(c)$, $f(c)-f(d)$, and $f(d)-f(a)$. Since $f(a) = a'$, $a'$ is a member of a $4$-cycle in $(G',E')$. With this contradiction, we find that there is no vertex of $(G',E')$ that is not a member of a $4$-cycle.

Answer 2

This statement can be proven directly from the definition of a graph isomorphism: a bijection between the vertex sets of the two graphs that preserves adjacency.

If you have never done this, you should do this at least once for some graph property. The idea is that if all vertices of $G$ are in a $4$-cycle, and $G$ is isomorphic to $H$, then given a vertex of $H$ you should be able to find a $4$-cycle it's in by finding a $4$-cycle containing the corresponding vertex of $G$. But you should fill in all the details yourself very carefully.

However, big-picture, you should not need to do this. All graph properties - properties of graphs that are determined just by knowing the vertices and the adjacencies between them - are preserved by graph isomorphism. (This excludes properties that assume specific names of vertices, an ordering on the vertex set, a specific embedding in the plane, or any other additional structure.) Every vertex being contained in a $4$-cycle is a graph property, so it is preserved by graph isomorphism.

Once you've proven this for one graph property, you know how to do it for all of them.