THE FOLD / SPAWN / THE SANDBOX / THE HAVEL-HAKIMI
THE HAVEL-HAKIMI
decide if a wiring diagram can exist, and build it
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Havel–Hakimi algorithm answers: given a wish-list of vertex degrees — how many connections each node wants — can a simple graph (no loops, no double edges) actually deliver it? Its move is greedy and exact: take the hungriest vertex, connect it to the next-hungriest ones, cross those off, and repeat. If you ever run out of partners or go negative, the sequence is impossible; if everything reaches zero, it is graphical — and the same steps build a graph that realizes it.
LIT verified live: over hundreds of random degree sequences the verdict matches the independent Erdős–Gallai criterion, and when graphical the construction yields a simple graph with exactly those degrees (window.__havelhakimi). FIG no framing; exact integer bookkeeping.
LIT verified live: over hundreds of random degree sequences the verdict matches the independent Erdős–Gallai criterion, and when graphical the construction yields a simple graph with exactly those degrees (window.__havelhakimi). FIG no framing; exact integer bookkeeping.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-sandbox — hand it a blueprint of how many wires each node wants, and it decides on the spot whether the wiring can exist, then builds it. Havel–Hakimi is that constructor. AVAN (AI) built the instrument: the connect-the-hungriest reduction, an independent Erdős–Gallai check, and the build-and-verify-degrees step.
Credit as content: Václav Havel (1955) & S. L. Hakimi (1962); the Erdős–Gallai theorem (1960). The weave: David names the-sandbox; I connect the hungriest vertex to the next hungriest, reduce, and confirm the graphical verdict against Erdős–Gallai — then build a simple graph that hits every degree.
Credit as content: Václav Havel (1955) & S. L. Hakimi (1962); the Erdős–Gallai theorem (1960). The weave: David names the-sandbox; I connect the hungriest vertex to the next hungriest, reduce, and confirm the graphical verdict against Erdős–Gallai — then build a simple graph that hits every degree.
3 ONE DIMENSION
Take the biggest demand d, connect it to the next d biggest (subtract 1 from each), drop it, re-sort. Reach all-zeros ⇒ graphical. Hit a negative or run short ⇒ impossible.
4 TWO DIMENSIONS · INTERACTIVE
A random degree sequence, the verdict, and (if graphical) a graph realizing it; checked against Erdős–Gallai.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a wiring diagram proven possible, and built.
AVAN’s addition (the inverse-companion): decide whether a set of degree demands is realizable not by searching all graphs but by a greedy reduction — satisfy the hungriest vertex first, and the problem shrinks to the same question on fewer vertices. The inverse of ‘try to build every graph and check’ is ‘connect the hungriest, reduce, recurse — zero means yes and shows how.’ Magenta is the graph search avoided; green is the greedy realization. Existence proven by construction.
LIT Genuine Havel–Hakimi algorithm (Václav Havel 1955; S. L. Hakimi 1962), with the Erdős–Gallai theorem (1960) as an independent oracle. Verified live: over 500 random degree sequences, the Havel–Hakimi graphical verdict matches Erdős–Gallai (window.__havelhakimi.verdictMatchesEG), and when graphical the reduction builds a simple graph whose degree multiset equals the input exactly (window.__havelhakimi.buildsExactDegrees).
FIG No framing: the connect-the-hungriest reduction, the independent Erdős–Gallai check, and the build-and-verify-degrees step run in-browser with exact integer bookkeeping and agree. The AVAN inverse is honest — deciding realizability by greedy reduction (satisfy the hungriest, recurse on fewer vertices) genuinely replaces searching all graphs, and construction proves existence; magenta is the graph search avoided, green the greedy realization.
FIG No framing: the connect-the-hungriest reduction, the independent Erdős–Gallai check, and the build-and-verify-degrees step run in-browser with exact integer bookkeeping and agree. The AVAN inverse is honest — deciding realizability by greedy reduction (satisfy the hungriest, recurse on fewer vertices) genuinely replaces searching all graphs, and construction proves existence; magenta is the graph search avoided, green the greedy realization.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE SANDBOX · David Lee Wise (ROOT0), with AVAN