# Prove that if $\delta \geq 4$, then graph $G$ contains at at least two even cycles.

*Edit: $$\delta$$ is the minimal vertex degree in the graph

So I've noticed a number of threads here on how to show that a graph with $$\delta \geq 2$$ contains a cycle but I can't find a way to prove the existence of two cycles and extending it to even cycles.

I've considered creating a subgraph $$G'$$ by removing edges of vertices with odd degree. Since $$\delta \geq 4$$, we'd be left with vertices that would be even and with a degree $$\geq 4$$. Assuming that $$G$$ is connected and each vertex degree is even, there must be an Eulerian cycle. Each vertex would be in the cycle at least twice because of $$\delta$$ so we'd be able to cut out the Eulerian cycle into a number of smaller cycles... but I'm not sure how to show that there will be even cycles.

Sorry for the inconsistent idea, I'm still new to proofs in Graph theory since the way of proving things here is very different from calculus or algebra.

• Might be worth explaining what $\delta$ is, for those who do not have access to the textbook you are using. Commented Mar 31 at 15:56
• @PrimeMover, thank you for the reminder. Commented Mar 31 at 16:00

Let $$v_1, v_2, …, v_n$$ be a maximal path in the graph. The degree of $$v_1$$ is at least $$4$$. Due to maximality of the path, all neighbours of $$v_1$$ belong to the path. Let them be $$v_2, v_i, v_j, v_k$$ in that order along the path.
Consider cycles $$C_1, C_2, C_3$$ from the picture. If two of them are even, then we’re done. If all are odd then the cycles $$C_1\cup C_2$$, $$C_2\cup C_3$$ are even. If only one of them is even (say $$C_3$$) then $$C_2\cup C_3$$ is also even.
By $$C_i\cup C_j$$ we denote the “embracing” cycle.
• Yes, since the degree of $v_1$ is $4$ and the path is maximal, the edges from $v_1$ go to the vertices of the path. Of course, cycles are created as shown in the picture. $C_1=(v_1v_2v_3…v_i)$, $C_2=(v_1v_iv_{i+1}v_{i+2}…v_j)$, $C_3=(v_1v_jv_{j+1}v_{j+2}…v_k)$.