Eulerian walk proof: If a connected graph has exactly two nodes with odd degree, then it has an Eulerian walk?

Question

Prove that: If a connected graph has exactly two nodes with odd degree, then it has an Eulerian walk. Every Eulerian walk must start at one of these and end at the other one. How shall I prove this?

Answer 1

Define the "total degree" to be the sum of all vertex degrees. Do induction on $k$, the total degree:

Base case: If there are any edges at all, the smallest total degree is $2$. Since the graph is connected, there must be only two nodes, and we just walk down the one edge. Done.

Let $k>1$, suppose the theorem is true for every graph with total degree $\leq k$, and suppose we have a graph (satisfying the hypotheses) with total degree $k+1$. Label $v_1$ and $v_2$ the only two vertices with odd degree. Starting at $v_1$, there are two cases:

1) there is an edge at $v_1$ which doesn't connect to $v_2$. Walk down that edge, and remove it from the graph (also remove $v_1$ if it has been disconnected). What is left over will still satisfy the hypotheses, the the total degree is now $k-1$, so there is an Eulerian walk.

2) Every edge at $v_1$ connects to $v_2$. Since we are beyond the base case there will be at least two edges, so starting at $v_1$ walk down any two edges and remove them from the graph (again, remove $v_1$ if it has been disconnected). The result will still satisfy the hypotheses (something to check here) and have total degree $k-3$, so we can walk.

(not totally rigorous, but I think it's a good sketch)