9
$\begingroup$

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.

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

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.

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

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Peter LeFanu Lumsdaine Dec 7 '12 at 20:46
  • $\begingroup$ I think we need to prove that such a path $\pi$ exists. $\endgroup$ – Amr Dec 7 '12 at 21:40
  • $\begingroup$ @Peter: The intersection of $c_1$ and $c_2$ is $\pi$. $\endgroup$ – Brian M. Scott Dec 7 '12 at 23:44
  • $\begingroup$ @Brian: yes — my comment referred to an earlier version of the answer. $\endgroup$ – Peter LeFanu Lumsdaine Dec 8 '12 at 1:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.