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