# Degree Sequence of a Graph

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.

-
The problem you are referring to is known as the handshaking lemma. –  Isaac Kleinman Mar 6 '12 at 14:46

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.

-
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