Clique
Named by 2 essays across one field — each of them below, with the objects they name alongside it.
Also named here as turan graph — the same set of essays touches all of them, so they are one junction rather than several.
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.
Named alongside it
The objects these essays reach for when they reach for this one.
Complete bipartiteEdge countExtremal graphTuran graphConvexityExhaustive searchGraphIndependent setInvariantOptimisationTriangle-free