Matpic
mathematics, in pictures
Concept

Cycle — where it appears

A closed walk in a network that returns to its start without reusing an edge; in a permutation, objects each sent to the next and the last back to the first. Cycles are what Euler's circuits are built from, and every permutation is a collection of disjoint ones.

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

The odd ring that forbids a stable pairing. The ranked lists of 6 people and a stable partition of them drawn on a circle: pairs as plain chords, a ring of three or more as arrows from each person to the one they hold. An odd ring is present, as it is in every stable partition of this instance.

A ring that no pairing can break

Put everybody in one pool and a stable pairing may not exist. Allow rings as well as pairs and something stable always exists — and the pairs-only answer fails exactly when that stable arrangement contains a ring of odd length. Two sides make every ring even, which is the whole reason the two-sided theorem holds.

applied · Stable matching 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.

Existence proofParityBlocking pairConstructionCounterexampleDegreeExhaustive searchGraphHierholzer's algorithmInvariantPermutationPreference profile

All concepts