3
$\begingroup$

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.

  • 0
    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.2012-05-03

2 Answers 2

5

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

  • 0
    Thank you for this reply. The graph has no loops or multiple edges. :)2012-05-03
2

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.