IBM Ponder This #011 · March 1999

If one person knows another, then the acquaintance is mutual. A clique is a set of four people in which every pair know each other.

Part A

There are $100$ people in a ballroom. Every person knows at least $67$ others.

Prove that there is a clique of four people.

Part B

Two people in the room, Joe and Grace, know each other.

Is there necessarily a clique of four people that includes both Joe and Grace?

Part C

There are actually $101$ people in the room, and every person still knows at least $67$ others.

Does the conclusion in Part A still hold?

Solution

Best opened after a real attempt

Solution

To be added.