Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

2 Answers

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
Yes, the nth vertex could have a degree greater than n, but then the same result holds. –  Jebruho Dec 5 '12 at 5:17
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.