6
$\begingroup$

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?

  • 0
    The assumption of connectedness isn't required; see Brian's answer, which does without it.2013-05-06

2 Answers 2

13

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.

  • 0
    @Anthony: The [pigeonhole principle](http://en.wikipedia.org/wiki/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$.2012-12-05
1

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.

  • 0
    Yes, the nth vertex could have a degree greater than n, but then the same result holds.2012-12-05