Thread: 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.

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

for all i.
Assume that no two vertices have the same degree, i.e.

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

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