Research effort:
$\rightarrow)$ I think this is relatively easy.
$\leftarrow)$ Let $G = (V,E)$, let $w$ be any vertex of $G$, given that all the vertex have even degree, I'm assured that I can construct a simple edge-disjoint cycle.
Now let's call this set of edges $S$.
Let $G' = (V,E/S)$
It's easy to see that given that I deleted a pair number of edges for each vertex (or none, in case the vertex was not part of the cycle), and every vertex in $G$ had a pair number of vertex, then, all the vertex in $G'$ have even degree or degree $0$.
Let $w'$ be a vertex in $G'$ whit degree more than $0$. I can construct another simple edge-disjoint cycle…
I can keep doing this procedure until all the vertex in the graph have degree $0$. And at this point I'll have decomposed $G$ into simple edge-disjoint cycles, then QED.
This proof is horrible, I can see some errors whit the reasoning, such when I say: "I'm assured that I can construct a simple edge-disjoint cycle".
Can you help me whit a more sound proof?
Best Answer
Your proof would be absolutely fine if we can prove that the construction of a simple edge disjoint cycle is always possible. Take any vertex u with a positive degree and start a tour on adjacent vertices until you are unable to explore further. Keep deleting the edges you have traveled. Assume you end at vertex v. What we have is a trail (not path): $$u,u_{1},u_{2}........v$$ The claim is, v has to be u.
Assume u and v are different. For every appearance of vertex v except the last one in the above list, there need to be two edges incident on v, one incoming and other outgoing. But for the last appearance, we need only one edge to enter the vertex v. Hence odd number of edges incident on v are used in the above trail. This leads to the fact there is at least one more edge on v yet to be explored. So the vertex v can not be the end of traversal. This proves u=v.
Now we have the circuit, which can be broken into disjoint edge cycles. How? For every two occurrence of a vertex y in the circuit, remove the circuit y-y from the parent circuit. Keep doing this recursively to get cycles.
Example: circuit $u,u_{1},u_{2},u_{3},u_{2},u$ be broken into $u,u_{1},u_{2},u$ and $u_{2},u_{3},u_{2}$
Since we have deleted the edges explored, the cycles have disjoint edges. We recursively keep finding circuits in the main graph, deleting the edges until we have explored all the edges. Which completes your proof.
An easy proof- let $G_{1}$,$G_{2}$,$G_{3}$... be connected components of the graph. Since the degree of each vertex is even there are Eulerian circuit for each component. Then the trails can be broken into disjoint cycles for each component.