9

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?

Brian M. Scott
  • 616,228
Anthony
  • 177
  • 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 05 '12 at 05:25
  • Yes I'm sorry I forgot to include that the graph is assumed to be simple and connected. – Anthony Dec 05 '12 at 05:30
  • The assumption of connectedness isn't required; see Brian's answer, which does without it. – joriki May 06 '13 at 14:50

2 Answers2

19

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.

Brian M. Scott
  • 616,228
  • 1
    How is the "mouseover" effect created? – Jebruho Dec 05 '12 at 05:21
  • 1
    @Jebruho: With >!. – Brian M. Scott Dec 05 '12 at 05:22
  • I'm not familiar with the pigeonhole principle could you explain it a bit? – Anthony Dec 05 '12 at 05:30
  • 1
    @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 05 '12 at 05:35
2

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.

Jebruho
  • 1,700