# How do I show that a simple graph of size n >= 2 always has at least two vertices of the same degree?

Asked by squaldig (5) February 7th, 2007
Observing members: 0 Composing members: 0

Here's one idea... just use counting:
ben (8419)
Start by picking the vertex with the highest degree, k
ben (8419)
we can assume k >= 2, (if it's 1, we're done).
ben (8419)
Now we know each connected vertex, k(i), must have a different degree (or we're done)
ben (8419)
so k actually must be > 3
ben (8419)
and then iterate through k(i) the same way... should be able to outnumber it
ben (8419)
I'm positive there's a far simpler solution, this was just my first idea... maybe it will help get the wheels turning
ben (8419)
Yeah, this should work. Just for the second step pick the vertex connected to k with the highest degree
ben (8419)
I don't see how that's a proof... It seems like more of a test for verification that this is true?
bhs (15)
It's an loose idea for a proof
ben (8419)
you're right, it's not a proof
ben (8419)
hmm... I don't think that will work formally... I think you need to start from the N=2 case and use induction to go up
bhs (15)
Okay, I was close, this proof is indeed much simpler:
ben (8419)
We assume there are no two vertices with the same degree
ben (8419)
so degrees must go from 0 to n-1 (we have n vertices, and an vertex can't connect to itself)
ben (8419)
but have a vertex with degree 0 and n-1 is a contradiction... the n-1 must be connected to every other vertex
ben (8419)
that should do it
ben (8419)
I think this is a pigeonhole argument: What are the possible degrees? 1 through n-1 (let's assume it's connected, else we just start with the smaller pieces). How many vertices? n. So two of them have the same degree by the pigeonhole principle.
finkelitis (1907)
what you said, ben
finkelitis (1907)
essentially
finkelitis (1907)

or