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.

I have a question about the proof of this theorem.

A graph is Eulerian $\iff$ it is connected and all its vertices have even degrees.

My question concerns "$\Leftarrow$"

Let $T=(v_0, e_1, v_1, ..., e_m, v_m)$ be a trip in Eulerian graph G=(V, E) where vertices can repeat but edges cannot. Let's consider T of the largest possible length. We prove that

(i) $v_0 = v_m$, and

(ii) $\left\{ e_i : i = 1, 2, . . . , m\right\} = E$ (but I think I understand everything about this part)

Ad (i). If $v_0 \neq v_m$ then the vertex $v_0$ is incident to an odd number of edges of the tour $T$. But since the degree $deg_G(v_0)$ is even, there exists an edge $e \in E(G)$ not contained in T. Hence we could extend $T$ by this edge — a contradiction.

What I don't understand here is why $v_0$ is incident to an odd number of edges.

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

You have a typo: it’s when $v_0\ne v_m$ that you can conclude that $v_0$ is incident to an odd number of edges of $T$. It’s incident to $v_1$, and any other vertices of $T$ to which it is incident must come in pairs, one just before it and one just after in the tour. But then, as you say, $T$ would not be maximal, so this is impossible, and we must have $v_0=v_m$.

share|improve this answer
    
You are right, that was a typo. Thanks for the explanation. –  Hagrid Feb 2 '13 at 21:20
    
@Hagrid: You’re welcome. –  Brian M. Scott Feb 2 '13 at 21:20
add comment

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.