4
$\begingroup$

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.

  • 0
    The problem you are referring to is known as [the handshaking lemma](http://en.wikipedia.org/wiki/Handshaking_lemma).2012-03-06
  • 0
    See [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?](http://math.stackexchange.com/questions/251310/if-n-is-a-natural-number-ge-2-how-do-i-prove-that-any-graph-with-n-vertic) and [Why do graph degree sequences always have at least one number repeated?](http://math.stackexchange.com/questions/1325896/why-do-graph-degree-sequences-always-have-at-least-one-number-repeated)2015-06-19

2 Answers 2

5

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.

  • 0
    And why can't the sequence 0,1,2,...,N-1 be a degree sequence? [signature removed by moderator]2010-08-11
  • 0
    If there is a vertex of degree N-1 in your graph on N vertices, every other vertex has degree at least 1.2010-09-01
3

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

  • 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.2010-08-11
  • 0
    so the degree sequence would be unique, obviously, and it cannot look like that because...my mind is drawing a blank...2010-08-11
  • 0
    Perhaps. For this problem, it felt more like an answer. [signature removed by moderator]2010-08-11
  • 0
    @Katie, @G. Paseman: Hints are acceptable as answers when they are hints because the answerer doesn't want to give away the problem2010-08-11