Graph theory proof

• April 21st 2009, 07:58 PM
tokio
Graph theory proof
Use graph theory to prove this statement:

a party of n people, n>=2, at least two people will have the same number of friends. Assume the relationship is symmetric or irreflexive.
• April 26th 2009, 09:01 PM
ZeroDivisor
Hi!

Let d_i be the number of friends of vertex i (in the friendship graph,
where vertices = party guests, edges = mutual friendship, no loops).
Then
$
0 \le d_i \le n-1
$

for all i.
Assume that no two vertices have the same degree, i.e.
$
d_i \neq d_j \; \mbox{for all} \; i \neq j
$

That means that for every possible degree there is exactly
one vertex with that degree. I.e., we may relabel the vertices
with the integers 0,1,..,n-1
so that after relabeling we have $d_i = i \; (i=0,..,n-1)$

But this graph does not exist!
Why?
Well, vertex n-1 is adjacent to all n-1 other vertices,
contradicting the fact that vertex 0 is not adjacent to anyone else.

qed

Best,

ZD