Friends and strangers theorem

The theorem states that among any six people, some three are pairwise friends or some three are pairwise strangers. It is the smallest nontrivial case of Ramsey’s theorem.

Connect

Ramsey theory: Ramsey theory studies conditions under which structure must appear in sufficiently large systems. The six-person result is the smallest nontrivial instance of its general existence principle.
Graph theory: Graph theory studies mathematical structures made of vertices connected by edges. The theorem’s people-and-relationships setup becomes a graph with six vertices.
Frank P. Ramsey: Frank P. Ramsey was an English mathematician, philosopher, and economist whose work founded Ramsey theory. His 1930 paper established the general theorem behind the six-person result.
Extremal graph theory: Extremal graph theory studies how many edges a graph can have while avoiding a specified subgraph. Its methods ask how far a network can avoid the patterns Ramsey theory eventually forces.
Ramsey number R(3,3): R(3,3) is the least number of vertices forcing a monochromatic triangle in every red-blue coloring of a complete graph. Its exact value, six, is precisely the numerical content of the theorem.
Pigeonhole principle: The pigeonhole principle says that placing more objects than containers forces at least two objects into one container. Among five relationships from one person, at least three share the same friend-or-stranger status.
Monochromatic graph: A monochromatic graph is a subgraph whose edges all have the same color in an edge-colored graph. A monochromatic triangle represents three people whose relationships all have one type.
On a Problem of Formal Logic: On a Problem of Formal Logic is Frank Ramsey’s 1930 paper proving a general theorem about unavoidable structure. The paper supplied the mathematical result later illustrated by the friends-and-strangers puzzle.
Social network: A social network represents people or organizations as nodes and their relationships as connections. The theorem’s original story is a structural claim about a network of acquaintances.
R(3,4): R(3,4) is the least number of vertices forcing a red triangle or a blue complete graph on four vertices in every two-coloring. It shows how quickly the corresponding guarantee grows when the target groups differ in size.