The Party of Six

The problem
6 people · every pair is friends or strangersprove: ∃ 3 mutual friends OR 3 mutual strangers

At a party, 6 people are present. Each pair of people either knows each other or doesn't — no in-between.

Prove that, no matter how friendships are distributed, there exist either:

  • 3 people who all know each other (a "friend triangle"), or
  • 3 people none of whom know each other (a "stranger triangle").