# If $n$ is a natural number $\ge 2$ how do I prove that any graph with $n$ vertices has at least two vertices of the same degree?

Any help would be appreciated.

If $n$ is a natural number $\ge 2$ how do I prove that any graph with $n$ vertices has at least two vertices of the same degree?

-
The result isn’t actually true for graphs in general; it is true, however, for simple graphs, i.e., graphs without loops or multiple edges, and I expect that those are the ones that you meant. –  Brian M. Scott Dec 5 '12 at 5:25
Yes I'm sorry I forgot to include that the graph is assumed to be simple and connected. –  Anthony Dec 5 '12 at 5:30
The assumption of connectedness isn't required; see Brian's answer, which does without it. –  joriki May 6 '13 at 14:50

HINT: The possible degrees of a simple graph with $n$ vertices are the $n$ integers $0,1,\dots,n-1$. However, a simple graph on $n$ vertices cannot have both a vertex of degree $0$ and a vertex of degree $n-1$; why?

That means that either the degrees of the $n$ vertices are all in the set $\{0,1,\dots,n-2\}$, or they’re all in the set $\{1,2,\dots,n-1\}$. How many numbers are in each of those sets? (In case that’s not enough of a hint, I’ve added a spoiler-protected further hint; mouse-over to see it.)

Pigeonhole principle.

-
How is the "mouseover" effect created? –  Jebruho Dec 5 '12 at 5:21
@Jebruho: With >!. –  Brian M. Scott Dec 5 '12 at 5:22
I'm not familiar with the pigeonhole principle could you explain it a bit? –  Anthony Dec 5 '12 at 5:30
@Anthony: The pigeonhole principle in its simplest form: If you put more than $n$ pigeons into $n$ pigeonholes, some pigeonhole has to contain at least two pigeons. Your pigeons are the vertices, an your pigeonholes are the available degrees. By the way, if the graph is connected, it’s even easier, since there cannot be vertex of degree $0$; thus, the available degrees are the numbers $1$ through $n-1$. –  Brian M. Scott Dec 5 '12 at 5:35

I will show only the case where no vertex has an edge going to itself. Assume a graph with $n$ vertices does not have at least two vertices of the same degree. Then one vertex has degree one, second vertex has degree two,..., $nth$ vertex has degree $n$, for some ordering of the vertices. Then the $nth$ vertex must be connected to $n$ other vertices. But then there are $n+1$ vertices, so that we have a contradiction.

-
Yes, the nth vertex could have a degree greater than n, but then the same result holds. –  Jebruho Dec 5 '12 at 5:17