MathDB

n

people attend a party. There are no more than

n

pairs of friends among them. Two people shake hands if and only if they have at least

1

common friend. Given integer

m\ge 3

such that

n\leq m^3

. Prove that there exists a person

A

, the number of people that shake hands with

A

is no more than

m-1

times of the number of

A

‘S friends.

Problem Statement