# Eulerian Graph Question

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.

-
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

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...

-
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.

-