0
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ where did you use the Eulerian circuit? $\endgroup$
    – Mano Mini
    Commented Feb 12, 2016 at 18:53
  • 1
    $\begingroup$ all vertices in a graph with a Eulerian circuit have even degree. $\endgroup$
    – JMP
    Commented Feb 12, 2016 at 18:54
  • $\begingroup$ 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"? $\endgroup$
    – Mano Mini
    Commented Feb 12, 2016 at 19:03
  • 1
    $\begingroup$ @ManoMini; made an edit, i changed my incorrect vertices into edges. is this better? $\endgroup$
    – JMP
    Commented Feb 12, 2016 at 19:10
  • $\begingroup$ How can you prove this using induction on the vertices' number $n$? $\endgroup$ Commented Feb 18, 2016 at 10:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .