General Question

squaldig's avatar

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 (5points) February 7th, 2007
Observing members: 0 Composing members: 0

20 Answers

ben's avatar
Here's one idea... just use counting:
ben (9080points)“Great Answer” (0points) Flag as…
ben's avatar
Start by picking the vertex with the highest degree, k
ben (9080points)“Great Answer” (0points) Flag as…
ben's avatar
we can assume k >= 2, (if it's 1, we're done).
ben (9080points)“Great Answer” (0points) Flag as…
ben's avatar
Now we know each connected vertex, k(i), must have a different degree (or we're done)
ben (9080points)“Great Answer” (0points) Flag as…
ben's avatar
so k actually must be > 3
ben (9080points)“Great Answer” (0points) Flag as…
ben's avatar
and then iterate through k(i) the same way... should be able to outnumber it
ben (9080points)“Great Answer” (0points) Flag as…
ben's avatar
I'm positive there's a far simpler solution, this was just my first idea... maybe it will help get the wheels turning
ben (9080points)“Great Answer” (0points) Flag as…
ben's avatar
Yeah, this should work. Just for the second step pick the vertex connected to k with the highest degree
ben (9080points)“Great Answer” (0points) Flag as…
bhs's avatar
I don't see how that's a proof... It seems like more of a test for verification that this is true?
bhs (15points)“Great Answer” (0points) Flag as…
ben's avatar
It's an loose idea for a proof
ben (9080points)“Great Answer” (0points) Flag as…
ben's avatar
you're right, it's not a proof
ben (9080points)“Great Answer” (0points) Flag as…
bhs's avatar
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 (15points)“Great Answer” (0points) Flag as…
ben's avatar
Okay, I was close, this proof is indeed much simpler:
ben (9080points)“Great Answer” (0points) Flag as…
ben's avatar
We assume there are no two vertices with the same degree
ben (9080points)“Great Answer” (0points) Flag as…
ben's avatar
so degrees must go from 0 to n-1 (we have n vertices, and an vertex can't connect to itself)
ben (9080points)“Great Answer” (0points) Flag as…
ben's avatar
but have a vertex with degree 0 and n-1 is a contradiction... the n-1 must be connected to every other vertex
ben (9080points)“Great Answer” (0points) Flag as…
ben's avatar
that should do it
ben (9080points)“Great Answer” (0points) Flag as…
finkelitis's avatar
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 (1907points)“Great Answer” (0points) Flag as…
finkelitis's avatar
what you said, ben
finkelitis (1907points)“Great Answer” (0points) Flag as…
finkelitis's avatar
essentially
finkelitis (1907points)“Great Answer” (0points) Flag as…

Answer this question

Login

or

Join

to answer.

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

Your answer will be saved while you login or join.

Have a question? Ask Fluther!

What do you know more about?
or
Knowledge Networking @ Fluther