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.


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.


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.