# Statements Equivalent to a Graph Being Eulerian

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 general

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

-
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

$\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?).