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?
Eulerian walk proof: If a connected graph has exactly two nodes with odd degree, then it has an Eulerian walk?
-
2Possible approach: Start by walking from one vertex of odd degree to the other, removing each edge after you traverse it. This leaves you with a graph with vertices of even degree only. – 2012-02-26
2 Answers
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)
-
0I was just wondering why you would explain two cases - ain't the first one enough no matter $v_1$ connects to $v_2$ or not? Thanks a lot! This is really helpful. – 2012-02-27
Let $(u, v)$ be the only two vertices of odd degree in your graph $G$. Consider $G'$ where you add an edge between $v, n$ to $G$. Then every vertex in the graph has even degree and is connected. Therefore you have a Eulerian circuit. Remove the edge and you get a Eulerian walk. Note that $G + e$ is not simple, as in, there may be more than one edge between two vertices. This is fine because Eulerian circuits still hold when we consider graphs that are not simple.