Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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'm struggling with the following question:

Prove that every Eulerian graph of odd order has three vertices of the same degree.

I'm not sure how to proceed with this. If someone could give me a boost it would be appreciated.

share|cite|improve this question
I don't know if this is the right way to go, but you might want to forget about Eulerian graphs temporarily, and start with the easier theorem that every connected graph has two vertices of the same degree. I think I can see where to go after that also, and maybe it'll be clear when you get there. – MJD May 3 '12 at 18:21
up vote 5 down vote accepted

Let $n=2k+1$ be the number of vertices. Then you have $2k+1$ vertices and the degree of each vertex is $2,4,6,..., 2k$. If you split $2k+1$ vertices into $k$ distinct groups, the pigeonhole principle says...

share|cite|improve this answer
Note that this result depends on assuming that the graph is simple (has no loop or multiple edges). This is rather amusing, since the Königsberg bridges graph has multiple edges. – Brian M. Scott May 3 '12 at 18:34
Yup good point :) – N. S. May 3 '12 at 18:38
Thank you for this reply. The graph has no loops or multiple edges. :) – janvdl May 3 '12 at 18:47

If your definition of Eulerian graph permits an edge to start and end at the same vertex the statement is not true. Think of a triangle with one extra edge that starts and ends at the same vertex. Vertex series $\{4,2,2\}$. If you don't permit this, see N. S.' answer.

share|cite|improve this answer

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.