Prove each edge can be part of exactly one simple circle $\iff$ graph contains an Euler cycle

Question

I have to prove the following:

Graph G has an Euler cycle $\iff $ We can divide G into simple circles such that each edge is part of exactly one circle

To be honest I have no idea even how to approach this. What I tried so far -

1. if we can divide G into simple circles than each vertex have an even degree $\Rightarrow$ we have an Euler cycle (I don't know how to prove that each vertex has an even degree)

2. the other direction - I tried doing using induction but I cant prove that I can remove a vertex in such way that wont destroy the even degree of all the other vertices

Please help.

Answer 1

Hints

1. If your remove a (simple) circle, the graph is still decomposable into circles. Since the circle was regular of degree two, by removing it each vertex degree either stayed the same or is decreased by exactly two. Can you turn this into an induction argument to show that a decomposable graph has only even vertex degrees (and therefore is Eulerian)?

2. Use induction on edge count and not on vertex count. Choose some vertex $v$. Starting at this vertex, follow the Euler cycle until it it closes to a circle the first time (not necessarily at $v$). Remove all edges of this sub-circle from the graph, and if some degree drops to zero then remove the corresponding vertex too. The resulting graph has still an Euler cycle (why?). Can you turn this into an induction argument to show that an Eulerian graph is decomposable into circles?