Clique
Named by 3 essays across one field — each of them below, with the objects they name alongside it.
The edge that forces a triangle
A graph on six points can carry nine edges with no three of them closing a triangle. It cannot carry ten. The bound is n²/4, the graphs that achieve it are all the same shape, and both facts fall out of examining every graph there is.
Moves that only ever add edges
Turán's theorem says the densest graph avoiding a complete graph on r + 1 points is the balanced r-part graph. Zykov's proof finds it by a sequence of moves — turn a point into a copy of a better-connected one it is not joined to — each of which adds edges and none of which can create the forbidden clique. A second proof spreads a unit of weight over the points and gets the same bound from a maximum.
No triangle, and four colours
A graph that contains four mutually joined points needs four colours. The converse looks obvious — a graph needing four colours should contain something like that — and it is false. Grötzsch's graph has eleven points, no three of them mutually joined, and needs four colours. Mycielski found a step that adds one colour to any graph without creating a triangle, so graphs with no triangle can need any number of colours, and their need is spread through the whole graph, with no part to point at.
Named alongside it
The objects these essays reach for when they reach for this one.
Complete bipartiteEdge countExhaustive searchExtremal graphTriangle-freeTuran graphChromatic numberConvexityGraphGraph colouringIndependent setInvariant