Six people, and three of them are always mutual friends or mutual strangers
Invite six people to a party. Any two of them either already know each other or they do not — there is no third option. Then no matter who you invite, and no matter how the acquaintances happen to fall, three of them will be mutual friends or three will be mutual strangers. You cannot choose a guest list that avoids it.
With five people you can dodge it. With six you cannot, and that single step from five to six is the smallest instance of the theorem this whole module is about: past a certain size, structure stops being optional.
Draw the six people as dots and every relationship as a line between them: red for friends, blue for strangers. Every pair gets a line, so there are fifteen in total. Your task is to colour all fifteen so that no triangle ends up in a single colour. Take a minute over it. The claim is not that it is difficult.
20 monochromatic triangles: 1–2–3 all friends, 1–2–4 all friends, 1–2–5 all friends, 1–2–6 all friends, …
There is no arrangement that works. Every one of the 32,768 colourings of six vertices contains one.
Click any edge to flip it between friends and strangers. The goal is to leave no triangle in a single colour. Five people allow it; six never do, and the second number below tells you how close you got.
Try it: Click any line to flip its colour. Switch to five people and the puzzle becomes solvable immediately — press Show a solution if you want to see one. Then switch back to six and watch the best you can manage stall above zero.
The reason is short enough to carry around in your head, and it turns on nothing more than the observation that five things sorted into two boxes must put three somewhere. That is the pigeonhole principle, and it does all the work.
Try it: Step through the argument. Notice that nothing in it depends on which person you started with, or on friendship rather than strangership — which is exactly why no guest list can escape.
If six always fails, five must sometimes succeed — otherwise the guarantee would start earlier. It does succeed, but only barely: out of 1,024 ways to colour the ten lines among five people, exactly twelve avoid a monochromatic triangle, and all twelve are the same picture with the labels moved around.
Of the 1,024 ways to two-colour five vertices, exactly 12 avoid a monochromatic triangle.
All twelve are the same arrangement relabelled: the red edges form a five-cycle around the outside, and the blue edges join every second vertex into a pentagram. Neither a cycle of length five nor a pentagram contains a triangle.
Every survivor splits its ten edges five and five — checked across all twelve.
These twelve are why R(3,3) is 6 rather than 5 — five people can be arranged to avoid the pattern, so the guarantee has to start one person later.
For six people there are 2¹⁵ = 32,768 colourings, which is few enough to simply look at all of them. That is a real proof, not a sample: if none of the possibilities works, none of the possibilities works. It is also the last time in this module that brute force will be of any use whatsoever.
This is the crudest possible argument and it works only because six vertices have fifteen edges. Add one person and the search grows to over two million colourings; reach the seventeen vertices needed for R(4,4) and it becomes 2¹³⁶, about 4 × 10⁴⁰. Checking a billion of those every second since the Big Bang would have covered roughly a hundred-trillionth of them. Brute force runs out almost immediately, which is why the rest of the subject exists.
Try it: Run both searches. The five-vertex case finds its twelve survivors; the six-vertex case finds nothing, and the number that matters is the zero.
The smallest party that forces three mutual friends or three mutual strangers is written R(3,3), and it equals 6. Ask for four mutual friends or four mutual strangers instead and the answer is R(4,4) = 18. Ask for five and nobody on Earth knows the answer — it is somewhere between 43 and 46, and that gap has resisted every computer ever pointed at it. The rest of this module is about how a question this easy to state gets that hard that fast, and what happened to it in 2023 and 2026.