To prove Euler's theorem about the existence Eulerian circuits, we need two parts, since the result is a set of necessary and sufficient conditions.
That the conditions are necessary is clear: any Eulerian circuit has to enter and leave each vertex exactly the same number of times, so that the indegree of each vertex must equal its outdegree -- or, for an undirected graph, the degree of each vertex must be even.
The difficult part of the proof is the sufficiency. Assume that we have a connected undirected graph where all vertices have even degree. We need to show that this graph has an Eulerian circuit. We use induction on the number m of edges. The basis is vacuously true for m=0, since such a graph has no edges and no vertices. (If you are uneasy with vacuous bases, consider the case m=3 -- each vertex has degree~2 and so the graph is just K_3, which clearly has an Eulerian circuit. The cases m=1 and m=2 cannot arise, since vertices could not all have even degree; and thus the theorem also holds vacuously in these cases.)
Assume then that the statement holds for all graphs of up to m-1 edges and consider a connected undirected graph G of m edges (m>3) where all vertices have even degree. (We ignore for a moment the question of whether such a graph does exist -- as we saw, no such graph exists for m=1 or m=2.) By an earlier result (Exercise 2.1), G must have a cycle. Remove the edges of this cycle from G to produce the subgraph G': this subgraph is an undirected graph on fewer edges where all vertices still have even degree. If G' is connected, we are done, since the inductive hypothesis applies and G' thus has an Eulerian circuit, to which we can add the cycle just removed to form an Eulerian circuit for G itself. The trouble is that the resulting graph need not be connected. However, each connected component must obey the inductive hypothesis (all of its vertices have even degree and it has fewer than n edges), so that each has an Eulerian circuit; moreover, the cycle that we originally removed intersects each of these circuits (otherwise the graph would not have been connected in the first place), so that we can construct an Eulerian circuit for the entire graph by moving along the cycle, entering an Eulerian circuit at the first intersection with a connected component, completing that circuit, and then following the cycle until it first intersects the next connected component, etc. (We take no special action when the cycle intersects a connected component for the second, third, or kth time, but just continue on the cycle.) The correctness of this step is clear, so that our inductive step is proved.
Finally, note that, even if no graph on m edges that satisfies the hypotheses exists, the step simply holds vacuously; thus we need not work on deriving some probably complex characterization of the values of m for which such graphs exist. But note that, in fact, such graphs exist for all values of m larger than~2: any simple cycle on k>2 vertices obeys the hypotheses of the theorem.