Complete bipartite
Named by 3 essays across one field — each of them below, with the objects they name alongside it.
Also named here as edge count, extremal 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.
The densest graph without a square
Forbid four points joined in a cycle and a graph can keep only about ½n^(3/2) of its edges — far fewer than the quarter of all pairs a triangle-free graph keeps. Counting pairs of neighbours proves the ceiling in two lines. What reaches it is not a random graph but a finite geometry: the points of a projective plane, joined when they are orthogonal.
Named alongside it
The objects these essays reach for when they reach for this one.
Edge countExtremal graphCliqueConvexityExhaustive searchTuran graphCounting two waysFinite fieldGraphIncidenceIndependent setInvariant