Why 6 People Force a Triangle

Every pair of people is either acquainted or strangers. We prove that there must be either 3 mutual acquaintances or 3 mutual strangers.
Party graph
Solid = acquainted · dashed = strangers
Acquainted Strangers

Case 1 — A has at least 3 acquaintances

Call three of them B, C, D.

If any pair among B, C, D are acquainted, that pair together with A forms a trio of mutual acquaintances.

If none of those three pairs are acquainted, then B, C, D are pairwise strangers.

Case 2 — A has at least 3 strangers

The exact same argument works with the relationship types reversed.

Either two of those three people are strangers to each other, giving a trio of mutual strangers with A, or all three know each other, giving three mutual acquaintances.

Therefore every 2-coloring of K₆ contains a monochromatic triangle.

Why this proves the result

Among the 5 edges touching A, at least ceil(5/2) = 3 have the same type by the pigeonhole principle. Once we choose those 3 people, the relationships among them force one of the two desired triangles.

This is the classic Ramsey-theory statement: R(3,3) = 6.