$[$Is connected$]$ & $[$Has a simple cycle of length $m$$]$ : An Analysis on Invariance

Question

How are the statements $$^{\dagger_1}\text{Is connected.}~~~~~^{\dagger_2}\text{Has a simple cycle of length $m$.}$$ an invariant?

Answer 1

You just do it. Suppose that $G=\langle V_G,E_G\rangle$ and $H=\langle V_H,E_H\rangle$ are isomorphic graphs, and suppose further that $G$ has a simple cycle of length $m$. Since $G$ and $H$ are isomorphic, there is a bijection $h:V_G\to V_H$ such that for each $u,v\in V_G$, $\{u,v\}\in E_G$ iff $\{h(u),h(v)\}\in V_H$. Let $\{v_1,v_2,\ldots,v_m\}$ be the vertices of a simple $m$-cycle in $G$, indexed in the obvious way: $\{v_k,v_{k+1}\}\in E_G$ for $k=1,\dots,m-1$, and $\{v_m,v_1\}\in E_G$. Then $\{h(v_k),h(v_{k+1})\}\in E_H$ for $k=1,\dots,m-1$, and $\{h(v_m),h(v_1)\}\in E_H$, and the vertices $h(v_1),\ldots,h(v_m)$ are distinct, so $\{h(v_1),\ldots,h(v_m)\}$ are the vertices of a simple $m$-cycle in $H$.

The proof for connectedness follows the same general scheme: show that $h$ carries paths in $G$ to paths in $H$.

Answer 2

Hints: Suppose that $G$ is a graph, and that $f:G\to G'$ is a graph isomorphism.

Suppose that $G$ is connected. Take any two vertices $u,v\in V(G')$. Consider the verticies $f^{-1}(u),f^{-1}(v)\in V(G)$. Since $G$ is connected there exists a path

$$f^{-1}(u)\to v_1\to\cdots\to v_m\to f^{-1}(v)$$

What happens if we look at the image of this path under $f$?

The simple cycle argument follows exactly the same. Find it in $G$ and push it forward to $G'$.

Answer 3

Let $\phi$ be an isomorphism of graphs $G,G'$, let $\psi$ be its inverse. Assume $G$ is connected. Then for any vertices $x,y$ in $G$, there is a path in $G'$ that connects $\phi x$ and $\phi y$. Then $\psi$ of this path connects $x,y$. Likewise $\phi$ (or $\psi$) gives you a cylce of length $m$ from a cycle of length $m$ in th eother graph.