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.

Theorem: Let G be a connected graph, then the following are equivalent

(i) each vertex of G has even degree

(ii)G has some cycles which between them use each edge of G once and only once

(iii) G is Eulerian

i don't quite get how to show (i)$\iff$ (ii). Also, it seems that (ii)$\implies$(i) is not quite right in generalenter image description here

see,there is cycle which use once and only once each of the edges of G but there are vertexes which are odd degree.

share|improve this question
    
For the condition to be true you have to end up at the same vertex where you start. Then $(ii)\Rightarrow (i)$ –  Daniel Montealegre Mar 16 '12 at 3:38
    
And I thought the definition of Eulerian was condition $(ii)$. –  Daniel Montealegre Mar 16 '12 at 3:38
    
Your conditions are equivalent to $G$ having a Eulerian cycle; "Eulerian graph" means a graph that has an Eulerian cycle;a graph that has an Eulerian path (a path that goes through every edge exactly once, but is not required to begin and end in the same place) is called "semi-Eulerian". The graph you draw has an Eulerian path, but not an Euler cycle. So it is not Eulerian, only semi-Eulerian. –  Arturo Magidin Mar 16 '12 at 4:10
    
@Graphth: The theorem doesn’t require that the graph be simple. –  Brian M. Scott Mar 16 '12 at 14:00

1 Answer 1

up vote 2 down vote accepted

$\bf{Hint:}$ For $(i)\Rightarrow (ii)$. Start at $v_1$ then go to a random vertex $v_i$ and then go out to another randomly chosen vertex. You will not get stuck at a vertex because the degree is even unless it is the vertex you started with (Why?). After this, the idea is to expand your cycle. If you have not already walked through every edge, then you can expand it (Why?).

Hope this helps.

share|improve this answer

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.