Matpic
mathematics, in pictures
Generator

Six people, and the trio that cannot be avoided

A generator in the discrete library, called 121 times across 25 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

All 16 trees on 4 labelled points. Every tree on 4 labelled points, drawn one by one. There are 16 of them, which is 4 to the power 2.

Four trees on seven points, gracefully labelled

Four trees on seven points, gracefully labelled. a path: 0 6 1 5 2 4 3; a star: 0 1 2 3 4 5 6; a caterpillar: 0 5 1 6 2 4 3; a spider: 0 1 4 5 3 6 2.

All twenty-three trees on eight points, gracefully labelled

All twenty-three trees on eight points, gracefully labelled. 23 trees on eight points, every one given a graceful labelling.

Every tree up to twelve points is graceful

Every tree up to twelve points is graceful. 2: 1 trees, mean 3, worst 3 steps; 3: 1 trees, mean 4, worst 4 steps; 4: 2 trees, mean 7, worst 9 steps; 5: 3 trees, mean 14, worst 20 steps; 6: 6 trees, mean 47, worst 70 steps; 7: 11 trees, mean 165, worst 295 steps; 8: 23 trees, mean 706, worst 1621 steps; 9: 47 trees, mean 2985, worst 10702 steps; 10: 106 trees, mean 13578, worst 81915 steps; 11: 235 trees, mean 65316, worst 711792 steps; 12: 551 trees, mean 333732, worst 6938283 steps.

How many graceful labellings trees have

How many graceful labellings trees have. 3 points: fewest 4, most 4, path 4; 4 points: fewest 4, most 12, path 4; 5 points: fewest 8, most 48, path 8; 6 points: fewest 12, most 240, path 24; 7 points: fewest 32, most 1440, path 32; 8 points: fewest 40, most 10080, path 40; 9 points: fewest 120, most 80640, path 120.

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.

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 labelling every tree seems to have

Number the points of a tree 0 to n − 1 and write on each edge the difference of the numbers at its ends. The labelling is graceful if the edges then carry 1 to n − 1, each exactly once. Every tree anyone has ever checked — every one of the 551 trees on twelve points, and every tree up to about thirty-five — has such a labelling, and no one knows why. A graceful tree also tiles a complete graph by rotation, which is why the question was asked.

 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

Almost every tree can be turned over

Cayley's n^(n−2) counts trees with labels on their points. Take the labels off and the count has no formula, because a symmetric shape absorbs labellings: the star on seven points can be labelled only seven ways, the one asymmetric shape 5,040. The bookkeeping that reconciles the two counts says something unexpected — almost every tree, labelled or not, can be turned over onto itself, where almost every graph cannot.

 Discrete

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.

 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

Every function is a tree with two marks

There are n to the n functions from n points to themselves, and n to the n − 2 trees on those points. André Joyal noticed in 1981 that the missing factor of n² is a choice of two points — a head and a tail — and that a function, read the right way, simply is a tree with a head and a tail. The reading turns Cayley's formula into one line and hands over a fact about random trees from the birthday problem.

 Discrete

Every point at the average of its neighbours

A planar graph can be drawn without crossings, but finding such a drawing looks like a search. Tutte found in 1963 that it is not: pin one face to a convex polygon, put every other point at the average of its neighbours, and the drawing that results has straight edges, convex faces and no crossings at all — provided no two points can cut the graph apart. It is the position a network of equal springs settles into, and it is also where a random walk expects to leave.

 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

How many shapes a tree can take

There are 262,144 labelled trees on eight points and only twenty-three shapes. Labels make counting easy — Cayley's nⁿ⁻² — and shapes make it hard, because a symmetric shape absorbs labellings. The count of shapes comes instead from a recurrence for trees with a root and a theorem of Richard Otter's for taking the root away: in every tree there is exactly one more class of points than of edges. Run to two hundred points, the counts grow like 0.535 × 2.9558ⁿ ÷ n^(5/2), and the same arithmetic counts the alkanes.

 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 crossings a graph cannot avoid

Five points all joined need one crossing, six need three, seven need nine. Euler's formula gives a lower bound that grows like the square of the number of points and is badly wrong; a sampling trick turns the same formula into a bound that grows like the fourth power and is right to within a constant. And for drawings with straight edges the count turns out to be something else entirely: the number of quadrilaterals the points make.

 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

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.

 Discrete

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.

 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