Matpic
mathematics, in pictures
Concept

Graph — where it appears

A set of points with a set of connections between them and nothing else — no distances, no angles, no positions. Everything else about a picture has been thrown away, which is what makes graph statements survive any redrawing.

Named by 32 essays across 8 fields — each of them below, with the objects they name alongside it.

Königsberg as a graph. The four landmasses as circles and the seven bridges as edges; every circle has an odd number of edges.

Seven bridges, and the invention of throwing things away

Euler solved a puzzle about a Prussian city by deleting the city. What survived the deletion was a new branch of mathematics.

discrete · Eulerian paths A wheel of 5 rim regions needs 4 colours. A hub touching 5 rim regions arranged in a ring. The rim is odd, so the whole map needs 4 colours and no fewer.

Four colours, and a proof nobody can read

Every map on a plane can be coloured with four colours so that no two neighbours match. The statement is understandable by a child, it resisted a century of attempts, and the proof that settled it cannot be checked by a human being.

discrete · Graph colouring V − E + F = 2, five times. Vertices, edges and faces of the five regular solids, with the alternating sum. The edges are counted from the faces rather than listed, and the sum is 2 in every row.

Every corner pays for itself

Count the corners of any solid, subtract the edges, add the faces. The answer is two. It is two for a cube, for a pyramid, for a football, for anything squashed or stretched — and the number is measuring the shape it is wrapped around rather than the shape itself.

topology · Euler characteristic 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, 5.

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 · Ramsey theory A majority cycle over 3 candidates, and how often 3 voters produce one. The majority tournament as a directed polygon with each arc's margin, beside one cell for every profile of the stated size, filled where no Condorcet winner exists.

The majority that goes in a circle

Every voter hands in a ranking, and a ranking is transitive by construction. Compare the candidates two at a time and let the majority decide each pair, and the verdicts need not fit together into a ranking at all.

applied · Voting rules The link that makes every traveller later. Four nodes and two routes, with the equilibrium flow and travel time before a zero-cost link is added between A and B and after. The travel time rises from 10 to 12.

The road that makes everyone later

An equilibrium is a state nobody can improve alone, which is a much weaker thing than a state anybody would choose. Adding a link that costs nothing to use makes every traveller in this network strictly slower, and the arithmetic says by exactly how much.

applied · Equilibrium A closed walk on the 3-cube changing one place at a time. The corners of a 3-dimensional cube with a path through every one of them exactly once, each step moving along an edge, and the last corner one step from the first.

A walk that changes one thing at a time

Counting from nothing to fifteen in binary changes four digits at once somewhere in the middle. There is another order through the same sixteen words in which every step changes exactly one — and it is a closed walk on a four-dimensional cube.

discrete · Hamiltonian cycles Two graphs that will not lie flat, and one that will. K4, K5 and K3,3 in the best straight-line drawings a search could find. K4 has no crossings; the other two have one each, and Euler's formula shows that none can have none.

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.

discrete · Planarity 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.

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 · Labelled trees A matching that covers all 5 of one side. A bipartite graph with every possible pairing drawn thin and one complete matching drawn thick, so that each vertex on the left is joined to a distinct vertex on the right.

One bottleneck and nothing else

A set of jobs can be filled by distinct people unless some group of jobs has too few candidates between them — and that single obstruction is the only one there is, which is what makes the theorem worth having.

discrete · Halls theorem The de Bruijn graph on 2 letters and words of 3, and the cycle through it. A graph whose vertices are short words and whose arrows are words one letter longer, with a closed walk using every arrow exactly once marked, and the cyclic sequence it spells.

Every word once, around a cycle

A cyclic string of eight bits holds all eight three-bit words, each exactly once — and the reason such a thing exists is that the constraint linking overlapping windows is itself the construction.

computation · De bruijn A wedge of 2 circles. Several circles all passing through one common point, each labelled with a generator, so that a loop is a word in those letters.

The subgroup that is freer than the group

A free group on two letters contains a subgroup of index three that is free on four. Nothing about a group makes that plausible; everything about a graph makes it obvious, and the argument is to stop looking at the group and start looking at the space whose loops it is.

topology · Covering spaces 17 points coloured by whether their difference is a square. 17 points on a circle with every pair joined, coloured by whether the difference of their labels is a square modulo 17; the largest set of points all joined by one colour has 3 members.

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 · Ramsey theory A determinant counting the 16 spanning trees. A small graph, the minor of its Laplacian, and every one of its spanning trees drawn as thumbnails.

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.

algebra · Determinant A four-by-four array holding every two-by-two block. A binary array, cyclic in both directions, drawn with its wrapped row and column, in which each of the sixteen two-by-two blocks appears exactly once.

A page that knows where it is

A four-by-four array of bits, cyclic in both directions, in which every two-by-two block appears exactly once. Print it repeatedly across a sheet and any four marks on that sheet are an address.

computation · De bruijn A cycle showing every pair from 5 things exactly once. The complete graph on 5 points with an Eulerian circuit drawn, and the cyclic sequence of symbols it spells; every window of two consecutive symbols is a different pair.

A cycle for every pair

A cyclic sequence in which every window of two consecutive symbols is a different pair of things. For five things it exists and for four it does not, and in both cases there are exactly as many pairs as there are places to put them.

computation · De bruijn Nineteen circles, one per vertex. A circle packing of a triangulation with seven interior vertices and twelve on the boundary: two circles touch exactly when their vertices are joined, and the radii were solved for rather than chosen.

Every flat graph is a pile of circles

A graph that can be drawn without crossings can be drawn in one particular way: as circles, one per vertex, touching exactly when their vertices are joined. The picture is not a choice — it is determined, up to the group two inversions generate.

geometry · Inversion A walk on a weighted graph, and a cycle whose traffic goes one way. A weighted graph with the long-run share of each state read off its total weight, beside a three-state cycle whose shares are equal and whose traffic circulates.

The chain that runs the same backwards

Put weights on the edges of a graph, step to a neighbour in proportion to them, and the long-run share of a state is its own weight over the total — read straight off the picture, with nothing to solve. The condition that makes that work is strictly stronger than being stationary.

probability · Markov chains The shortest tree was already in the triangulation. The Delaunay triangulation of 20 sites in faint lines with the minimum spanning tree drawn over it in heavy ones. Every tree edge is a triangulation edge, and the circles on the longest few tree edges as diameters contain no other site.

The tree inside the triangulation

The shortest network joining a set of points is built from edges chosen by length, and the triangulation is built from edges chosen by an emptiness condition about circles. The two constructions share no step, and every edge of the first is an edge of the second.

geometry · Voronoi The 14 triangulations, joined by single flips. The flip graph of a 6-gon: 14 triangulations drawn as small polygons and joined by 21 edges, one for each pair differing in a single diagonal.

The solid whose corners are triangulations

Take the triangulations of a hexagon as points and join two of them when a single diagonal can be swapped for another. The result is not merely a graph — it is the edge skeleton of a genuine convex polyhedron, with fourteen corners, three square faces and six pentagonal ones.

discrete · Catalan numbers A landscape nobody is looking at, and every move goes downhill on it. The 8 states of a congestion game with 3 participants and two resources, ordered by Rosenthal's potential, with every improving unilateral move drawn as an arrow. Every arrow points downward.

The landscape nobody is looking at

Letting participants move one at a time to whatever is currently better can cycle forever, and on a network of congestible roads it cannot. The reason is a single number attached to each state that falls by exactly what the mover saves.

applied · Equilibrium 3 symmetries over 3 sheets: a regular covering. A 3-sheeted covering of a wedge of 2 circles, with the permutations of its sheets that commute with every generator. There are 3, against 3 sheets.

The symmetries a cover has of its own

A covering space can be shuffled without disturbing anything below it, and how many ways there are is decided by the subgroup it corresponds to. When there are as many symmetries as sheets the covering is called regular, and that is the same statement as the subgroup being normal.

topology · Covering spaces 6 vertices folded to 4, and a graph that decides. The graph built from 3 generator words, folded until no vertex has two edges of one label leaving it. Reading a word from the base vertex decides membership, and 6 words are tested.

Folding a graph until it decides

A subgroup of a free group usually arrives as a list of words, and almost nothing about it is readable from the list. Draw the words as loops, merge every pair of edges with the same label leaving one point, and what is left is a machine that decides membership by reading.

topology · Covering spaces A network of six places and the tree that holds all fifteen of its cheapest cuts. A network with capacities on its roads beside a tree on the same places, whose edge numbers give the cheapest cut between any two places as the smallest number on the path joining them.

One tree for every cut

A network of six places has fifteen pairs, and each pair has its own cheapest cut. All fifteen can be read off a tree with five numbers on it: the cheapest cut between any two places is the smallest number on the tree's path between them. Gomory and Hu proved in 1961 that such a tree always exists, and building it takes five cuts, not fifteen.

discrete · Network flow 5 two-literal clauses drawn as 10 arrows. The literals of four variables arranged in a circle with an arrow for each implication a two-literal clause contains, the arrows forming a path from one literal to its negation and back highlighted, beside the list of clauses and their arrows.

Two literals make an arrow

A clause of two literals, p ∨ q, says that if p is false then q is true, and if q is false then p is true — two arrows. A set of such clauses is a directed graph on the literals, and it is unsatisfiable exactly when some variable and its negation reach each other. Each of those two paths is a chain of resolution steps, and finding them takes time proportional to the size of the input.

logic · Resolution A matching of 4 and a cover of 4. A bipartite graph with its largest matching drawn thick and a smallest set of vertices meeting every edge ringed, the two having the same size.

What the search has when it fails

A largest matching is easy to find and hard to certify: the claim that nothing larger exists is a claim about every arrangement not tried. The certificate turns out to be free — it is the wreckage of the search that failed.

discrete · Halls theorem A graph whose matching misses 2 of its 10 vertices. A graph with its largest matching drawn thick, a set of vertices ringed, and the pieces left when that set is deleted marked by whether they hold an odd number of vertices.

The piece that cannot pair off

Take the sides away and the obstruction to a matching changes character completely. It is no longer a shortage of partners; it is a parity, and the quantity that measures it counts pieces of odd size rather than vertices of any size.

discrete · Halls theorem 2 independent cycles and 3 independent cuts, on 5 edges. A small graph beside its incidence matrix, with the matrix's rank and nullity given and shown to be the number of independent cuts and the number of independent cycles.

The cycles and the cuts

The count that splits a map's source into what dies and what survives has nothing to do with graphs. Apply it to a matrix built from a graph's edges and points and it says that a graph's independent cycles and its independent cuts add to its number of edges — a theorem about drawings, obtained from an array.

algebra · Linear maps Breadth-first levels in a planar triangulation. A Delaunay triangulation of 160 random points with each point coloured by whether it is inside, on or outside the level 4 steps from the centre; that level of 23 points separates 31 from 106.

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 · Planarity Zykov's moves, from 10 edges to 16. 6 panels showing a graph on 7 points with no complete graph on 4, changed one move at a time; the edge count rises 10, 11, 12, 13, 14, 16 and ends at Turán's graph.

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 · Extremal graphs Hierholzer's construction on 6 vertices and 9 edges. Three views of one graph whose vertices all have even degree: a first closed walk that stops back at its start, the loops walked from vertices on it with edges left over, and the single circuit made by splicing them, with every edge numbered in order.

A walk that splices in its own detours

Euler proved that a walk crossing every bridge once needs every landmass to have an even number of bridges, and then stated, without proof, that this was enough. The missing half took 137 years, and it is not an argument but a procedure: walk until stuck, notice that stuck can only mean home, and splice in a detour from anywhere with edges left. The procedure never fails, and the reason fits in one sentence about arriving and leaving.

discrete · Eulerian paths The postman's route: 24 blocks of street, walked in 28. A street network with its odd-degree vertices marked and the streets a shortest closed route must walk twice drawn doubled, dashed in a second colour, pairing up the odd vertices.

The streets a postman walks twice

A postman must walk every street of a district and come back. If every corner has an even number of streets, no street needs walking twice. If not, some must — and the ones repeated always join the odd corners in pairs. Pricing every way of pairing them finds the shortest round; pairing the nearest corners first does not.

discrete · Eulerian paths

Named alongside it

The objects these essays reach for when they reach for this one.

Counting argumentExistence proofParitySpanning treePlanar graphComplete graphExhaustive searchMatchingPlanarityCovering spaceDe bruijn sequenceDeficiency

All concepts