Does a 3-regular graph necessarily contain a cycle of even length?
I tried, believe me I tried, I even went and asked my professor's assistant and even he couldn't give me a straight answer...
So...please help?..
$\endgroup$1 Answer
$\begingroup$I assume we're talking about simple finite graphs. (An infinite cubic graph need not contain any cycles at all; a "loopy" cubic graph need not contain any cycle of length greater than one; a graph with parallel edges contains cycles of length two.)
Yes, every cubic ($3$-regular) graph contains an even cycle. It will suffice to show that the graph contains a "theta" subgraph, i.e., two distinct vertices connected by three internally disjoint paths. Two of the three paths will have lengths of the same parity, so their union will be the desired even cycle.
Let $G$ be a cubic graph. Without loss of generality, we may assume that $G$ is connected. Let $v$ be a vertex of $G$ which is not a cut-vertex, i.e., $G-v$ is connected. (E.g., any vertex of maximum eccentricity is not a cut-vertex.) The vertex $v$ is adjacent to $3$ distinct vertices $x,y,z$ of $G-v$.
Since $G-v$ is connected, $x$ is connected to $y$ by a path $x_0,x_1,\dots,x_m$ in $G-v$, with $x_0=x$ and $x_m=y$. Now let $z_0,z_1,\dots,z_n$ be a path of minimum length in $G-v$ connecting $z$ to $\{x_0,x_1,\dots,x_m\}$, with $z_0=z$ and $z_n=x_j$. Now it's easy to see that $x_j$ is connected to $v$ by three internally disjoint paths in $G$, one through each of the vertices $x,y,z$.
P.S. I guess we don't need regularity; the same argument works for any graph with minimum degree at least $3$.
$\endgroup$
