Edge count
Named by 4 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.
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.
Every two edges must meet
A planar drawing has edges that avoid each other. Turn the rule round and insist that every two edges meet exactly once, at a shared end or a single crossing, and the drawing is what John Conway called a thrackle. In the 1960s he conjectured that a thrackle can never have more edges than points, and put up a prize. With straight edges a short argument settles it, and the argument also bounds the longest distances in a set of points. With curved edges it is still open.
Named alongside it
The objects these essays reach for when they reach for this one.
Complete bipartiteExhaustive searchExtremal graphCliqueConvexityTuran graphConjectureCounting two waysCrossing numberExtremal problemFinite fieldGraph