Eulerian graph has three vertices of the same degree

Question

Let $G$ be a connected graph with $n \ge 3$ vertices.

Prove that if $G$ has an Euler Cycle than it has 3 vertices of the same degree.

I thought using the Pigeonhole principle but I'm not sure how...

Thanks !

Answer 1

Since $G$ is connected, every vertex has positive degree. Since $G$ has an Eulerian cycle, every vertex has even degree.

If $n$ is even then the degree of each vertex lies in $\{2,4,\ldots,n-2\}$ which has $(n-2)/2$ elements. If there are at most 2 vertices of each degree then $G$ has at most $2((n-2)/2)=n-2$ vertices which is a contradiction.

If $n$ is odd then the degree of a vertex lies in $\{2,4,\ldots,n-1\}$ which has $(n-1)/2$ elements. If there are at most 2 vertices of each degree then $G$ has at most $2((n-1)/2)=n-1$ vertices which is a contradiction.

Answer 2

I can do it if the graph is finite. That must be an assumption if you're thinking pigeonhole principle right?

If every edge is visited exactly once in a cycle all degrees of vertices must be even (why?).

if n=3 and connected then it's the complete graph on 3 vertices and they all have the same degree.

Proceed by induction. Suppose it's true for n.

Consider a connected graph with an euler circuit with n+1 vertices. If you take two edges that share an edge you can take a quotient going them together which also removes said edge. Note the total number of edges each vertex would have without the edge is odd so the resulting vertex in the quotient is even degree so there's still an eulerian circuit.

The induction hypothesis gives 3 vertices with the same degree in the quotient. If none of the merged vertex we are done.

Note the argument would work for any 2 adjacent vertices so pick the two so that the new degree is as large as possible. Now it's not possible it could be one of the three otherwise another vertex should have been chosen