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.

I am trying to brush up my graph theory skills. I have not done any in over 4 years and i am rusty...If someone could help me out with this simple proof i would appreciate it.

Prove that for any graph $G$ of order at least 2, the degree sequence has at least one pair of repeated entries.

So the degree sequence if a list of the degrees of each vertex (usually written in descending order).

I know that the sum of the degrees of the vertices of a graph is equal to $2|E|$ and that the number of vertices of odd degree is even.

If someone could help me out and point me in the right direction i would appreciate it.

share|improve this question
    
The problem you are referring to is known as the handshaking lemma. –  Isaac Kleinman Mar 6 '12 at 14:46
add comment

2 Answers 2

up vote 5 down vote accepted

Yes, it just came to me after i posted the comment to the previous answer.

A graph with at least 2 vertices and no edges the 0 degree is repeated. A graph with 2 vertices and 1 edge the degree 1 is repeated. Each vertex has at least one entry in the degree sequence, so there are a total of $N$ entries. But each degree can have a maximum of degree = $N-1$. Therefore according to the pigeonhole principle at least one of the degrees has to repeat.

share|improve this answer
    
And why can't the sequence 0,1,2,...,N-1 be a degree sequence? [signature removed by moderator] –  G. Paseman Aug 11 '10 at 17:12
    
If there is a vertex of degree N-1 in your graph on N vertices, every other vertex has degree at least 1. –  Serge Gaspers Sep 1 '10 at 22:18
add comment

If there were no repeats, what would the degree sequence look like? Why could it not look like that?

share|improve this answer
1  
I'd probably add such hints/questions as a comment rather than an answer--then if the OP figures it out from those he can post a full answer himself. –  Jamie Banks Aug 11 '10 at 0:26
    
so the degree sequence would be unique, obviously, and it cannot look like that because...my mind is drawing a blank... –  gprime Aug 11 '10 at 1:35
    
Perhaps. For this problem, it felt more like an answer. [signature removed by moderator] –  G. Paseman Aug 11 '10 at 3:35
    
@Katie, @G. Paseman: Hints are acceptable as answers when they are hints because the answerer doesn't want to give away the problem –  Casebash Aug 11 '10 at 7:55
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.