Eulerian paths — the series

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.

part 1 · discrete

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.

part 2 · discrete

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.

part 3 · discrete

Every edge on exactly two cycles

Draw a graph on paper without crossings and its faces are cycles, each edge on exactly two of them. George Szekeres and Paul Seymour asked in the 1970s whether every graph without a bridge has such a set of cycles, drawn on paper or not. The Petersen graph needs five, the flower snark on twenty points five as well, every random graph tried has one, and nobody has proved it — though a minimal counterexample would have to be a snark.

part 4 · discrete

Two arrows in and two out

An Eulerian circuit enters every point as often as it leaves, so it hands every edge an arrow with the arrows balanced at each point. Count those balanced orientations instead of the circuits and the question turns into the ice in a freezer: on the square grid, where every point has two arrows in and two out, there are about 1.5396 of them per point — Lieb's (4/3)^(3/2), against Pauling's guess of 1.5. Fix the walls of a square of ice and the count becomes 1, 2, 7, 42, 429, 7436: the alternating-sign matrices.

part 5 · discrete

Three arrows in and three out

Put an arrow on every edge of the cubic grid so that every point has three arrows in and three out. On the square grid the same question — two in, two out — has an exact answer, found by Elliott Lieb in 1967: about 1.5396 arrangements per point. On the cubic grid nobody knows the answer. Pauling's guess of 2.5 is a proven lower bound, and exact counts on prisms of the grid come down towards it from above — 2.794, 2.682, 2.587 as the cross-section widens — without reaching it.

part 6 · discrete