Generator

The bridges of Königsberg

A generator in the discrete library, called 42 times across 9 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.

euler-path 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

The bridges of Königsberg. A schematic of the city: a river splitting around an island, four landmasses, and the seven bridges joining them.

A cycle showing every pair from 5 things exactly once

Arriving and leaving come in pairs

The de Bruijn graph on 2 letters and words of 3, and the cycle through it

A four-by-four array holding every two-by-two block

One cycle of 8 letters holding all 8 words of length 3

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 final circuit: step 1 walks along the edge it names ×28
Fleury's walk: step 1 walks along the edge it names ×6
the walk after the imaginary bridge is removed: step 1 walks along the edge it names ×5
the first-edge walk: step 1 walks along the edge it names ×3
the number of cycles for words of 2 letters matches 2^(2^(n−1) − n) ×3
the strings of length 4 found come in whole rotations ×3
and 2 in ×2
every vertex has 2 edges out ×2
a closed circuit needs every degree even ×1
a closed circuit over every edge visits one more vertex than it has edges ×1
a closed walk over every edge visits one more vertex than it has edges ×1
a walk from a vertex of even degree can only get stuck where it started ×1
after removing a cycle every degree is still even ×1
all four landmasses have odd degree ×1
an even degree pairs every arrival with a departure ×1
an odd degree leaves exactly one edge unpaired ×1
an open walk needs exactly two odd degrees ×1
and each exactly once ×1
and none of them appears twice ×1
and one edge per word ×1
and runs from one odd landmass to the other ×1
and the greedy rule gives the greatest of those that begin with n zeros ×1
and the position found is the one the patch was taken from ×1
each word is smaller than all its rotations ×1
every vertex drawn is a vertex used ×1
every window of two consecutive symbols is a different pair ×1
every word of the right length appears in the cycle ×1
Fleury's walk uses every edge ×1
Fleury's walk: one edge between each pair of consecutive stops ×1
Fleury's walk: the walk closes ×1
in a graph of even degrees a walk on unused edges never meets a dead end ×1
in the other direction too ×1
it crosses every real bridge once ×1
Königsberg has seven bridges ×1
landmass E has degree 3 ×1
landmass I has degree 5 ×1
landmass N has degree 3 ×1
landmass S has degree 3 ×1
no cyclic sequence of 6 symbols shows every pair from 4 exactly once ×1
no Euler walk exists ×1
pairing the closest two first costs 6 ×1
the alphabet has two or three letters ×1
the best pairing costs 4 ×1
the circuit uses every pair once ×1
the concatenation is a de Bruijn sequence ×1
the count grows with the word length ×1
the cycles use every edge exactly once ×1
the degrees add to twice the number of edges ×1
the even panel really shows an even degree ×1
the example graph is a path or a circuit ×1
the final circuit: one edge between each pair of consecutive stops ×1
the final circuit: the walk closes ×1
the first walk gets stuck with edges left over ×1
the first-edge walk stalls with edges unused ×1
the first-edge walk: one edge between each pair of consecutive stops ×1
the first-edge walk: the walk closes ×1
the graph drawn has at most nine vertices ×1
the graph has one vertex per word one letter shorter ×1
the graph is one of the even-degree examples ×1
the greedy rule also produces a de Bruijn sequence ×1
the ground set has between four and seven elements ×1
the lengths of the necklaces add to the number of words, which is Witt's identity ×1
the necklace concatenation is the least de Bruijn sequence ×1
the network is one of the postman examples ×1
the number of odd vertices is even, since the degrees add to twice the edges ×1
the odd panel really shows an odd degree ×1
the patch appears at exactly one position of the array ×1
the patch is taken from inside the sheet drawn ×1
the route is every street once plus the cheapest pairing's paths ×1
the rows are not all de Bruijn sequences in their own right ×1
the search runs to words of three or four letters ×1
the sequence is as long as the number of words ×1
the sixteen positions give sixteen different blocks ×1
the spliced tour uses every edge ×1
the torus drawn is the four-by-four one ×1
the view is one the family draws ×1
the walk after the imaginary bridge is removed: one edge between each pair of consecutive stops ×1
the walk uses every edge ×1
the windows are all different ×1
the words are between two and five letters long ×1
the words are between two and four letters long ×1
the words are listed in lexicographic order ×1
two landmasses have odd degree ×1
vertex A has even degree ×1
vertex B has even degree ×1
vertex C has even degree ×1
vertex D has even degree ×1
vertex E has even degree ×1
vertex F has even degree ×1
vertex O has even degree ×1
with the chosen paths doubled every degree is even ×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.

Computation

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

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.

Discrete

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

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.

Topology

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.

Computation

Every necklace, in order

The graph construction needs the whole graph in memory and finds one sequence among hundreds of millions. Listing the necklaces in alphabetical order and writing them end to end needs no graph at all, and produces the smallest of them.

Computation

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.

Discrete

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

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.

The whole library · What the figures prove