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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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|cite|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

Your Answer


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.