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
    @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.