Extremal graphs — the series
-
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.
-
The fewest triangles an edge density allows
Half of all possible edges can be drawn without a single triangle. One more, and triangles appear — not one but several at once. Push the density further and the question becomes a curve: for every share of edges, the fewest triangles a large graph can hold. The answer is a string of scallops, touching a simple parabola at the densities of the balanced multipartite graphs and bulging above it between them. It was guessed in the 1980s and proved in 2008 by a method that turns counting into positive-definite matrices.
-
As many points as two steps allow
In a graph where every point has d neighbours and every point is within two steps of every other, there can be at most d² + 1 points — one, its d neighbours, and d(d − 1) more reached through them. Graphs that meet the bound exactly are rare to the point of absurdity. The pentagon does it for d = 2, the Petersen graph for d = 3, a fifty-point graph found in 1960 for d = 7, and an eigenvalue argument proves there is nothing else — except possibly one graph with 3,250 points and 57 neighbours each, which nobody has found or ruled out.
-
Triangle-free, and two-sided eventually
Every graph with no triangle and the most edges possible is bipartite. Erdős, Kleitman and Rothschild proved that almost every triangle-free graph is bipartite too — and yet among the 246,348,115 triangle-free graphs on nine labelled vertices, fewer than half are. The share falls before it rises, and the reason is that small graphs are sparse.