I recently received as an exercise the statement « 2-connected graphs that contain no even cycle as a subgraph have a very simple structure. » I then had to describe that structure and prove it.
I did not really have a revelation about which direction to take so this is what I did. I know it is probably not correct at some point or that there might be a lot of theorems that I didn’t think of that would have made this easier :
Let $G$ be an arbitrary 2-connected graph that contains no even cycle as a subgraph. Since $\forall H \subseteq G$, $H$ is not an even cycle, $G$ has no even cycle in its structure. Also, due to $G$’s 2-connectivity, we know that :
- $G$ cannot be a tree
- $G$ contains no cutvertex
- $G$ contains no bridge
- $G$ contains at least one cycle (specifically an odd cycle in this case, I am not sure if this point 4 is correct/relevant to assume or not)
With this in mind, intuitively, I thought that $G$ had to be a graph whose structure can only contain odd cycles « glued to one another », meaning odd cycles that are joint by the edges they share.
But then, I showed that it is not possible for $G$ to be made of multiple odd cycles that share edges since, if two odd cycles share edges, there exists a cycle $C$ around the edges of $C_1 \cup C_2 \setminus X$, where $C_1$ and $C_2$ are the two odd cycles and $X:=C_1\cap C_2$ is the set of the edges they share, such that $C$ is of even length.
To show that $C$ is of even length, note first that $\lvert C_1\rvert$ + $\lvert C_2\rvert$ is even since it is the sum of two odd numbers. Take P the path along the edges of X, let $v_1$ and $v_n$ be the endpoints of P. The path $v_1C_1v_nC_2v_1$ is the cycle $C$. $\lvert C\rvert = \lvert C_1 \cup C_2\setminus X\rvert$. We can also write this equation as $\lvert C\rvert = \lvert C_1\rvert - \lvert X\rvert + \lvert C_2\rvert - \lvert X\rvert = \lvert C_1\rvert + \lvert C_2\rvert - 2\lvert X\rvert$, which is clearly even.
Thus, this means that $G$ does not contain more than one odd cycle (since if it contains 2 or more, any pair of odd cycles induces an even cycle), which means that $G$ is itself an odd cycle.
Is this result correct and is this a valid proof ?