# 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
## 20 Answers

Here's one idea... just use counting:

Start by picking the vertex with the highest degree, k

we can assume k >= 2, (if it's 1, we're done).

Now we know each connected vertex, k(i), must have a different degree (or we're done)

so k actually must be > 3

and then iterate through k(i) the same way... should be able to outnumber it

I'm positive there's a far simpler solution, this was just my first idea... maybe it will help get the wheels turning

Yeah, this should work. Just for the second step pick the vertex connected to k with the highest degree

I don't see how that's a proof... It seems like more of a test for verification that this is true?

It's an loose idea for a proof

you're right, it's not a proof

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

Okay, I was close, this proof is indeed much simpler:

We assume there are no two vertices with the same degree

so degrees must go from 0 to n-1 (we have n vertices, and an vertex can't connect to itself)

but have a vertex with degree 0 and n-1 is a contradiction... the n-1 must be connected to every other vertex

that should do it

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.

what you said, ben

essentially

## Answer this question

This question is in the General Section. Responses must be helpful and on-topic.