Six People, Two Relationships

Issue 33 Core Published 28 Oct 2026 By The Chalkboard Desk

The problem

At a party there are people. Every pair of them either knows each other or does not, and the relation 'knows' is mutual. Show that among the six there is always either a set of three people who all know one another, or a set of three who are pairwise unacquainted. Then show that for people this is false.

Knowing is symmetric: if A knows B then B knows A.
You are asked for a triple in one of the two relationships, not for a fixed one.

Take a minute

Reveal hint 1

Pick one person. Five relationships lead out of them, and only two colours — the pigeonhole principle gives you three of one kind.

Reveal hint 2

Draw the six people as a graph with two colours of edge and look for a monochromatic triangle.

Solution

AnswerEvery -colouring of the edges of contains a monochromatic triangle; can be coloured without one, so .

Derivation

Model the party.
Pick a vertex.
Split into two cases.
Handle the other colour.
Disprove the case .
State the conclusion.

Margin notes

Take the people as vertices and colour each edge red if the pair knows each other, blue otherwise. The claim becomes: every -colouring of has a monochromatic triangle.
Fix a person . The edges from are coloured with colours, so at least of them share a colour. Say knows , and .
If any two of , , know each other, that pair together with forms a red triangle. Otherwise none of , , knows another, and they form a blue triangle.
The same argument with the colours exchanged covers the case where is unacquainted with three people.
Arrange people in a cycle and let each know only their two neighbours, with the remaining pairs unacquainted. Then the acquaintances form a -cycle with no triangle, and the strangers form the complementary -cycle, also with no triangle.
Because always forces a monochromatic triangle while never does, the Ramsey number equals .