# A finite, undirected, connected and simple graph with Eulerian circuit has $3$ vertices with the same degree

Let $G=(V,E)$ a finite, undirected, connected and simple graph, $|V| \ge 3. \space$

Prove: If $G$ has Eulerian circuit then $G$ has $3$ vertices with the same degree.

As the graph is simple each vertex can have at most $n-1$ edges, of which at there are at most $\lfloor{\dfrac{n-1}{2}}\rfloor$ elements with an even number of edges. For example, if $n=20$, a vertex can have only members of $\{2,4,6,8,10,12,14,16,18\}$ for it's edge count.

By the Pigeonhole Principle, $n$ vertices into $\lfloor{\dfrac{n-1}{2}}\rfloor$ elements results in $3$ vertices with the same degree.

• where did you use the Eulerian circuit? Commented Feb 12, 2016 at 18:53
• all vertices in a graph with a Eulerian circuit have even degree.
– JMP
Commented Feb 12, 2016 at 18:54
• you used it in "of which at there are at most $\lfloor{\dfrac{n-1}{2}}\rfloor$ elements with an even number of vertices." ? I don't understand this phrase... "elements"? Commented Feb 12, 2016 at 19:03
• @ManoMini; made an edit, i changed my incorrect vertices into edges. is this better?
– JMP
Commented Feb 12, 2016 at 19:10
• How can you prove this using induction on the vertices' number $n$? Commented Feb 18, 2016 at 10:47