1
$\begingroup$

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$.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Nitpick: $a-b-c-a$ is a $3$-cycle, not a $4$-cycle. $\endgroup$ – Misha Lavrov Apr 12 '18 at 3:02
  • $\begingroup$ @MishaLavrov : I'd like to claim that this was a plan to subtly thwart plagiarism. I'd like to claim it, but ... It's really just an off-by-one error. Fixing... $\endgroup$ – Eric Towers Apr 12 '18 at 3:04
  • $\begingroup$ @Eric Towers: I see, you spelled out the argument given referred to by MishaLavrov. Thanks, this way is much better. $\endgroup$ – user394438 Apr 12 '18 at 3:06
  • 1
    $\begingroup$ @user394438 : This is true. You should also practice writing this (and similar likely preserved by isomorphism properties), understanding why each sentence is the right thing to write -- that is, this should just flow from you easily. It takes a little practice, but only a little. It also trains your eye what to look for in properties that are not preserved by isomorphism. $\endgroup$ – Eric Towers Apr 12 '18 at 3:09
1
$\begingroup$

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.

$\endgroup$

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.