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.
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
$\displaystyle
0 \le d_i \le n-1
$
for all i.
Assume that no two vertices have the same degree, i.e.
$\displaystyle
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 $\displaystyle 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