Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
I take it you’re assuming that G is finite? –  Peter LeFanu Lumsdaine Dec 7 '12 at 20:33

2 Answers 2

up vote 7 down vote accepted

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.

share|improve this answer
    
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.

share|improve this answer
    
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
    
Thanks, that seems to conclude it. –  Cain Dec 8 '12 at 12:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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