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.

Printable View

- Apr 21st 2009, 08:58 PMtokioGraph 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. - Apr 26th 2009, 10:01 PMZeroDivisor
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