Graph Theory. Induction Hypothesis.

Question

I would like prove that: A graph contains an Eulerian cycle if and only if the graph is connected and every vertex has even degree. I'm going to try this by induction. How I can formulate the induction hypothesis?

Answer 1

One direction is immediate, without induction. For the other, an attempt by induction on the number of vertices, say, is a bit tricky: For example, it is not completely straightforwad how to obtain a smaller graph with only even.degree vertices by removing a vertex and some (but which?) edges; and then it is not completely straightforward how to obtain a Eulerian cycle of the original graph from a Eulerian cycle of the smaller graph.

Instead, I suggest you reformulate the claim to also handle graphs with exactly two odd vertices and Euler paths with these vertices as end points. In that formulation, an induction on the number of edges is quite straighforward.