Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
Possible 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. –  Alex Becker Feb 26 '12 at 18:14

1 Answer 1

up vote 2 down vote accepted

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)

share|improve this answer
    
I 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. –  Jean Feb 27 '12 at 1:42

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.