In graph theoretic terms, we want to prove that if $G$ is a graph whose vertices have degree $\ge3$ then we can find an even cycle. Suppose not. Pick a vertex $v_0$ and consider its neighbours $v_{11},v_{21}\dots, v_{k1}$, $k\ge3$. Consider for example $v_{11}$. If all of his neighbours belonged to the set $\{v_0, v_{21}, \dots, v_{k1}\}$ we could find a $4-$cycle. Hence it has a neighbour $v_{12}$ that doesn't belong to this set. Define similarly $v_{i2}$ for the other $v_i$'s with $i\neq 0$. Note that they are distinct, otherwise a $4-$cycle would be formed. We keep adding vertices in a similar way so that $v_{im}$ is connected to $v_{i(m-1)}$ and is different from all the vertices defined before. This process must end: pick for instance the vertex $v_{1r}$ where $r$ is maximum. Hence the neighbours of $v_{1r}$ belong to the set of vertices defined before. Suppose it's connected to $v_{ab}$ and $v_{ac}$ with $a\in\{1,\dots, k\}$ and WLOG $b<c$. If $b$ and $c$ have the same parity an even cycle can be formed as follows: $v_{ab}v_{a(b+1)}\dots v_{ac}v_{1r}v_{ab}$. If they don't then one between $v_0,v_{11},v_{12},\dots,v_{1r}, v_{ab}, v_{a(b-1)},\dots, v_0$ and $v_0,v_{11},v_{12},\dots,v_{1r}, v_{ac}, v_{a(c-1)},\dots, v_0$ is even. Then, suppose that $v_{1r}$ is connected to $v_{ab}$ and $v_{cd}$ with $a\neq c$: then one of $v_0,v_{11},v_{12},\dots,v_{1r}, v_{ab}, v_{a(b-1)},\dots, v_0$ and $v_0,v_{11},v_{12},\dots,v_{1r}, v_{cd}, v_{c(d-1)},\dots, v_0$ and $v_{1r}v_{ab}, v_{a(b-1)},\dots, v_0, v_{c1}\dots v_{cd}v_{1r}$ is even.

After reading this post before no one replied I went on to solve this problem unfortunately I was beaten The solution is different though: Define a "pretzel" to be a union of two cycles as follows: $v_1,v_2...v_m$ is one cycle and $v_1,w_1....w_k,v_l$ is a path. Notice that there are three different paths between $v_1$ and $v_l$ hence some two different paths have the same parity, connected these paths together to form a cycle we see it must therefore have even length. So what we want to do now is show that there must exist such a "pretzel", this can be proven by contradiction: Obviously our graph has some cycle $v_1,v_2...v_m$ now start from $v_1$ and you can walk out of this cycle (as there must be some other edge connected to $v_1$ by problem condition), now if we keep walking out of each vertex we see that we form a new cycle, do the same to this new cycle, pick a vertex in it that we have only so far visited once and hence you can keep walking out and hence forming a new cycle. If on your walk you stumble back on to a previously formed cycle(or a path between two previously formed cycles) then you clearly have yourself a pretzel therefore we can keep continuing this process forever and hence form infinitely many cycles, a contradiction

kamil9876 wrote: Notice that there are three different paths between $v_1$ and $v_l$ Maybe I'm wrong, but I don't think this is necessarily true. The remaining edge from $v_1$ could lead to vertices that are not otherwise connected to the cycle if not via $v_1$, and the same could be for the other $v_i$'s. This would leave just two paths from $v_1$ to $v_l$, that is, the ones of the cycle.

Yes of course you are right, a priori this does not need to hold. You misread my post though (not your fault but rather my casual writing style), what I first showed is that if we have such a "pretzel" then the problem is solved, then my next part of the post deals with showing that there must exist such a "pretzel", namely the second half of my post starting from here: Quote: So what we want to do now is show that there must exist such a "pretzel", this can be proven by contradiction:

Gotcha. I read it in a hurry before!