The Party Problem

Combinatorics · Axiom Academy

A beautiful result in Ramsey Theory: at any party of 6 people, either 3 are mutual friends or 3 are mutual strangers We represent the party as a complete graph K 6 with 6 vertices (people). Each edge between two people is colored: Blue edge = the two people know each other (friends) Red edge = the two people don't know each other (strangers) Every pair of people must be connected by exactly one edge, colored either blue or red. 2. Applying the Pigeonhole Principle Choose any person (call them Person A). Person A is connected to 5 other people. By the pigeonhole principle : if we have 5 edges in 2 colors, at least 3 edges must share the same color. Without loss of generality, assume Person A has at least 3 blue edges (the argument is symmetric for red). 3. Analyzing the Three Connected People Person A has blue edges to (at least) three people: B, C, and D. Now consider the triangle formed by B, C, and D. Each of the three edges (BC, CD, BD) is colored either blue or red. Case 1: If any edge among B-C-D is blue , say B-C is blue, then we have a blue triangle : A-B-C (all mutual friends). Case 2: If all three edges among B-C-D are red , then B-C-D forms a red triangle (all mutual strangers).

This is the written version of the interactive lesson above. See the full Combinatorics course.