Generator

Six people, and the trio that cannot be avoided

A generator in the discrete library, called 71 times across 16 essays. Below: what it draws with nothing chosen and at each mode an essay asks for, what it checks while drawing, and everywhere it is used.

complete-graph is one function. Everything below came out of it during this build, at parameters taken from the essays rather than invented for this page — so a figure here is the same figure a reader meets in an essay, and if the generator changes, this page changes with it.

With nothing chosen

Six people, and the trio that cannot be avoided. The fifteen pairs among six people, coloured at random. Whatever the colouring, three people are all mutual acquaintances or all mutual strangers — here 1, 2, 3.

All 16 trees on 4 labelled points

A random labelled tree on 60 points

The degree of a point in a random tree on 7 points

How many leaves the 16,807 trees on 7 points have

The share of a random tree that is leaves

$The share of a random tree that is leaves. A falling curve of the expected fraction of leaves in a random labelled tree against the number of points on a logarithmic axis, with sampled values as dots and a dashed line at one over e.$

What it checks while it draws

Collected by running the family and recording what it asserted, not written here. The count is how many separate times the claim was put to the test while these drawings were made.

the branch sets of 0 and 1 are joined by an edge ×13
the 2-point witness has no four-cycle ×8
on 3 points, avoiding a complete graph on 3 allows Turán's count ×7
K5: a subdivision of K5 is also a minor ×6
the plane over 2 gives a graph with no four-cycle ×5
there is some n at which the expected count of 4-sets is below one ×5
and the codes are all 3 sequences of length 1 ×4
on 3 points no two trees share a code ×4
10 to 120 points ×3
K4: the counting bound and the best drawing found agree about whether it lies flat ×3
K5, drawn flat as a solid's skeleton, has neither ×3
K5: an edge joins two different points of the graph ×3
K5: the minor test and the subdivision test agree about planarity ×3
the best weighting scores ½(1 − 1/ω) with ω = 2 ×3
and 6 is below the known R(4,4) of 18 ×2
cube: a subdivision of K5 is also a minor ×2
K5 with a point split: a subdivision of K5 is also a minor ×2
K5: the best drawing found has one crossing ×2
octahedron: a subdivision of K5 is also a minor ×2
Petersen graph: a subdivision of K5 is also a minor ×2
the grid side is between 6 and 20 ×2
the most triangle-free edges on 6 points is ⌊n²/4⌋ ×2
there are exactly n to the n minus two trees on 4 labelled points ×2
Wagner graph: a subdivision of K5 is also a minor ×2
2 to 4 cars ×1
a named graph ×1
a plane over the field with 2, 3 or 5 elements ×1
a plane small enough to draw its pairs ×1
a point's degree is one more than its count in the Prüfer sequence ×1
a tree is given as a list of pairs of points ×1
a tree with more than one edge always has a leaf to strip ×1
a vertex meets five others ×1
after contracting the spokes, all ten pairs of the five merged points are joined ×1
after deletion the random graph has no four-cycle ×1
and every pair gets one colour either way round ×1
and in fact at least two, which is Goodman's bound ×1
and it contains a subdivision of K3,3, so it is not planar ×1
and it has at most 2d + 1 points for a tree of depth d ×1
and it is reached at a balanced split ×1
and it is the edge count of the balanced two-part graph ×1
and no move creates the forbidden clique ×1
and no tree is listed twice ×1
and on this many points it is the most any such graph has ×1
and respects the cherry bound ×1
and that is more than two thirds of the grid ×1
and the bound for graphs with no triangle rules out K3,3 ×1
and the layout kept is one a reader can follow ×1
and the next size up is the first with an expectation of at least one ×1
and the trees, built one by one, number the same ×1
and the two colours take half the pairs each ×1
at least one colouring is tried, and at most twenty thousand ×1
at least one level is balanced ×1
between 30 and 200 points ×1
branch sets are disjoint ×1
cars is read only by the parklist view ×1
counting every tree gives the binomial law for the degree ×1
cube, drawn flat as a solid's skeleton, has neither ×1
cube: an edge joins two different points of the graph ×1
cube: the minor test and the subdivision test agree about planarity ×1
each clique size counted is between 3 and 8 ×1
each clique size is a whole number between 3 and 8 ×1
each pair of neighbours of a point is a pair with that common neighbour, and none is counted twice ×1
each path runs along edges of the graph ×1
each piece holds at most half of its parent ×1
enough well-spaced points were placed ×1
EVERY colouring of six people contains a monochromatic triangle ×1
every edge the extremal graph is missing would complete a triangle ×1
every free row joins the free column's component, so that component holds at least k points per free row ×1
every move strictly adds edges ×1
every pair has at most one common neighbour ×1
every pair is coloured exactly once ×1
every point has three neighbours ×1
every tree is drawn for between 3 and 5 points ×1
exactly one of the n + 1 rotations of a list empties the last spot ×1
fewer removed points than rows leave free rows and a free column ×1
five edges in the pentagon ×1
five to nine points ×1
K5 has ten edges ×1
K5 with a point split contains a subdivision of K3,3 ×1
K5 with a point split contains no subdivision of K5 ×1
K5 with a point split, drawn flat as a solid's skeleton, has neither ×1
K5 with a point split: an edge joins two different points of the graph ×1
K5 with a point split: the minor test and the subdivision test agree about planarity ×1
K6 has fifteen edges ×1
minus one is itself a square, so the rule does not depend on which way round the pair is taken ×1
moving a point to a smaller part adds edges ×1
no triangle has all three edges the same colour ×1
no two edges of the triangulation cross ×1
no two points share two neighbours, so there is no four-cycle ×1
no weighting beats it ×1
octahedron, drawn flat as a solid's skeleton, has neither ×1
octahedron: an edge joins two different points of the graph ×1
octahedron: the minor test and the subdivision test agree about planarity ×1
on the circle each preference is one of the n + 1 spots ×1
on the circle every list parks every car and leaves exactly one spot empty ×1
Petersen graph contains a subdivision of K3,3 ×1
Petersen graph contains no subdivision of K5 ×1
Petersen graph, drawn flat as a solid's skeleton, has neither ×1
Petersen graph: an edge joins two different points of the graph ×1
Petersen graph: the minor test and the subdivision test agree about planarity ×1
prefs is a list of 3 to 7 preferred spots, each between 1 and the number of cars ×1
prefs is read only by the parking and parkcircle views ×1
q + 1 points are orthogonal to themselves ×1
sampled trees have the predicted share of leaves ×1
six to fifteen points ×1
so the cherries are at most the pairs ×1
so the parking functions are (n + 1)^n / (n + 1) of the lists ×1
some fundamental cycle leaves at most two thirds on each side ×1
some level leaves at most two thirds on each side ×1
stretching the drawing to fill its panel changes no crossing ×1
the bijection is checked up to between 3 and 6 points ×1
the bound is of the order of 2 to the k over 2 ×1
the code is two shorter than the number of points ×1
the colouring is drawn on 5, 13 or 17 points, each a prime one more than a multiple of four ×1
the colouring treats its two colours alike, so the largest sets match ×1
the decoded tree has one edge fewer than points ×1
the dial has a radius between 40 and 400 ×1
the drive and the sorting test agree on whether every car parks ×1
the end is Turán's graph and Turán's count ×1
the enumeration matches Rényi's count of trees with k leaves ×1
the even weighting on a largest clique reaches the same score ×1
the exhaustive search finds a K5 minor as well ×1
the expectation is swept to between 20 and 200 points ×1
the extremal graph splits the points in two with every edge crossing ×1
the first complete graph the bound rules out is K5 ×1
the forbidden clique has three to five points ×1
the forbidden complete graphs have between three and five points ×1
the graph has q(q + 1)²/2 edges ×1
the graph is connected ×1
the graph is small enough for bitmask search ×1
the graph searched is the Petersen graph, the split K5 or the Wagner graph ×1
the K3,3 columns never part ×1
the K5 columns part on exactly the split K5 and the Petersen graph ×1
the labelled points number between 3 and 7 ×1
the largest count is the balanced split's ×1
the last spot stays empty exactly when the list is a parking function on the line ×1
the majority colour is one of the two ×1
the mean number of leaves is n(1 − 1/n)^(n − 2) ×1
the Paley colouring is drawn on 5, 13 or 17 points ×1
the parking functions number (n + 1)^(n − 1) ×1
the parking functions of length n number the labelled trees on n + 1 points ×1
the paths share no interior point, and pass through no branch point ×1
the Petersen graph has K5 as a minor and not as a subdivision ×1
the Petersen graph's shortest cycle has five edges ×1
the plane beats the random graph and stays under the bound at every size ×1
the plane has q² + q + 1 points ×1
the recursion is shallow enough to colour ×1
the result is complete multipartite ×1
the search found a layout that is not degenerate ×1
the search runs on between three and six points ×1
the search runs to between five and nine points ×1
the seed is a whole number the colouring can be drawn from ×1
the sweep runs to between 20 and 200 points ×1
the table or the check runs to a size the enumeration can reach ×1
the table runs to between 5 and 12 points ×1
the table runs to between four and six points ×1
the thinnest balanced level grows like √n: its ratio to √n stays within a narrow band ×1
the thinnest balanced level is within the square-root scale ×1
the three ends make three pairs, and any one of them closes a trio ×1
the tree drawn has one fewer edge than it has points ×1
the tree encoded has between 4 and 7 points ×1
the triangle bound allows it and the girth bound does not ×1
the view is one the family draws ×1
the Wagner graph has no K5 minor ×1
the Wagner graph has no K5 minor but a K3,3 minor ×1
they are exactly the lists whose sorted form never exceeds its positions ×1
this colouring has a monochromatic triangle ×1
two colours over five edges forces three of one ×1
two of the three cannot be drawn flat ×1
Wagner graph, drawn flat as a solid's skeleton, has neither ×1
Wagner graph: an edge joins two different points of the graph ×1
Wagner graph: the minor test and the subdivision test agree about planarity ×1
while it allows the two that can be drawn flat ×1
while the level itself grows several-fold ×1
with at most one part fewer than the forbidden clique ×1

Where it is called

Every figure on this list is drawn by the same rule, so a change to the rule changes all of them at once. That is why the list is published.

Algebra

A determinant that counts trees

Write down a graph's Laplacian, strike out one row and its column, take the determinant. The answer is the number of spanning trees — and the minus signs in the determinant are what cancel every subset of edges that is not one.

Discrete

A random tree is one part in e leaves

Choose a labelled tree on n points uniformly at random. A point is a leaf exactly when its label never appears in the tree's Prüfer code, so the share of leaves is (1 − 1/n)^(n − 2) — half the points for a tree on four, 36.8% for a large one, the reciprocal of e. The whole degree distribution follows the same way: one plus a Poisson count with mean one.

Discrete

Cars that park, and trees that grow

Three cars arrive at a one-way street with three spaces; each has a favourite space, drives to it, and takes the first free one from there on. Of the 27 lists of favourites, exactly 16 let every car park — the same 16 as the labelled trees on four points. The reason is a circular street with one extra space, on which every list parks and exactly one rotation of it leaves the extra space empty.

Discrete

Counting the colourings

Asking whether a graph can be coloured with four colours gives a yes or a no. Asking how many ways there are gives a polynomial — and the polynomial answers the first question, and several others nobody asked.

Discrete

Eighteen people, and the seventeen that escape

Among any eighteen people, four are mutual acquaintances or four are mutual strangers. Seventeen can be arranged so that neither happens, and the arrangement is not a lucky find — it is a rule about squares.

Discrete

Five spokes squeezed into K5

The Petersen graph has no point with four neighbours, so no stretched copy of K5 can sit inside it. Contract its five spokes and K5 appears anyway. Kuratowski's theorem forbids stretched copies and Wagner's forbids squeezed ones, the two notions disagree on this graph — and they still name exactly the same planar graphs.

Discrete

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.

Discrete

Seven regions on a doughnut

A map on a torus can need seven colours, and the proof is a picture — seven regions, each sharing a border with all six others. The plane needed a computer and eighty-six years; the harder surface was settled in 1890 by drawing something.

Discrete

Six people at a party

Among any six people, three are mutual acquaintances or three are mutual strangers. Five is not enough, and the arrangement that saves five is a pentagon. Beyond that the numbers become unknowable.

Discrete

Sixteen trees on four points

How many ways are there to connect n labelled points into a single tree? The answer is n to the power n minus two, which is a strange enough formula to demand an explanation — and the explanation is a code that turns every tree into a short list of numbers, and every short list of numbers back into a tree.

Discrete

The colouring nobody has ever seen

Count the monochromatic sets a random colouring is expected to contain. If the average is below one, some colouring has none — and the argument is finished, having produced nothing anyone can look at.

Discrete

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.

Discrete

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.

Discrete

The few points that cut a flat graph

Any graph that can be drawn without crossings, however large, falls into pieces of at most two thirds once a few points are removed — about the square root of its size, never more than 2.83 times it. A grid shows the square root cannot be beaten, a ring of breadth-first neighbours comes close, and a cycle through a shallow tree finishes the job.

Discrete

Two graphs that will not lie flat

Five points, every pair joined: no matter how the points are placed or how the lines are drawn, two of the lines cross. The proof is not about drawing at all — it counts edges against faces and finds one edge too many.

Topology

Two trees, and every edge in exactly one of them

Euler's formula is usually proved by deleting things until nothing is left. There is a better argument that deletes nothing — a tree through the corners and a tree through the faces, which between them use every edge once and can therefore be counted.

The whole library · What the figures prove