# Even cycles in a graph

I'm at a dead end with the following question, It seems simple enough but I cant seem to see it.

Let G be a simple undirected graph with minimal degree 3, show that G contains an even cycle.

Thanks.

• I take it you’re assuming that G is finite? – Peter LeFanu Lumsdaine Dec 7 '12 at 20:33

Consider the maximal path $P$ in the graph G. Let it be $u_1u_2...u_k$. By the maximality of the path $P$, we know that all neighbors of $u_1$ belong to {$u_2,u_3,...,u_k$}. Since $3\leq \deg(u_1)$, let $u_i,u_j$ be two neighbors of $u_1$ such that $2<i<j$. Now it is easy to show that one of the following cycles must be even: $$u_1u_2..u_iu_1$$ $$u_1u_2..u_ju_1$$ $$u_1u_iu_{i+1}..u_{j-1}u_ju_1$$

This is becasue the sum of lengths of all three cycles $=(i)+(j)+(j-i)=2j$ is even, thus it is impossible that the three lengths are odd.

• You can get $\deg$ with \deg. – Brian M. Scott Dec 7 '12 at 23:39

Hint 1:

Find a cycle $c$ in $G$ and a path $\pi$ that connects two vertices of $c$ without using an edge of $c$. The path splits $c$ into two cycles $c_1$ and $c_2$. If both $c_1$ and $c_2$ are odd cycles, then the paths $c_1 \setminus \pi$ and $c_2 \setminus \pi$ are either both even or both odd. Hence $c$ is in this case even.

Hint 2: In order to find $c$ and $\pi$ take first all bridges out. Then take any cycle in a component that is not a cycle.

• In the third case, don’t we need to be a bit careful, since the intersection of $c_1$, $c_2$ could contain more edges than just $e$, and indeed may not even be connected? – Peter LeFanu Lumsdaine Dec 7 '12 at 20:46
• I think we need to prove that such a path $\pi$ exists. – Amr Dec 7 '12 at 21:40
• @Peter: The intersection of $c_1$ and $c_2$ is $\pi$. – Brian M. Scott Dec 7 '12 at 23:44
• @Brian: yes — my comment referred to an earlier version of the answer. – Peter LeFanu Lumsdaine Dec 8 '12 at 1:38