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, 07: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, 09: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

$\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