Matpic
mathematics, in pictures
Concept

Hierholzer's algorithm

The procedure that builds a closed walk using every edge of a graph exactly once, by walking until stuck and splicing in detours from vertices with edges to spare. It is a proof as well as a method: the splicing fails only when the degree condition does.

Named by 3 essays across 2 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 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 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

Named alongside it

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

GraphDegreeParityAbstractionConstructionCountingCycleCyclic wordDe bruijn sequenceEncodingEulerian circuitExhaustive search

All concepts