2
$\begingroup$

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.

  • 0
    For the condition to be true you have to end up at the same vertex where you start. Then $(ii)\Rightarrow (i)$2012-03-16
  • 0
    And I thought the definition of Eulerian was condition $(ii)$.2012-03-16
  • 0
    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.2012-03-16
  • 0
    @Graphth: The theorem doesn’t require that the graph be simple.2012-03-16

1 Answers 1

2

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