THE FOLD / LOOT / THE BOUNTY / THE TUTTE POLYNOMIAL
THE TUTTE POLYNOMIAL
one recursion counts every subgraph family
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Tutte polynomial T(G; x, y) is the master invariant of a graph: a single two-variable polynomial from which a whole zoo of counts falls out by plugging in numbers. It is built by deletion–contraction with special cases for loops and bridges, and its evaluations count structures — T(1,1) is the number of spanning trees, T(2,1) counts spanning forests, T(1,2) counts connected spanning subgraphs, and T(2,2) = 2edges counts all subgraphs. One recursion, many combinatorial answers.
LIT verified live: over hundreds of random connected graphs, T(1,1), T(2,1), T(1,2) and T(2,2) match brute-force counts of spanning trees, forests, connected spanning subgraphs and all edge-subsets (window.__tutte). FIG no framing; the deletion–contraction recursion and the exhaustive counts both run in-browser.
LIT verified live: over hundreds of random connected graphs, T(1,1), T(2,1), T(1,2) and T(2,2) match brute-force counts of spanning trees, forests, connected spanning subgraphs and all edge-subsets (window.__tutte). FIG no framing; the deletion–contraction recursion and the exhaustive counts both run in-browser.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-bounty — one polynomial that pays out a whole bounty of counts, a different treasure at each evaluation point. AVAN (AI) built the instrument: the deletion–contraction recursion with loop/bridge rules, and brute-force counters for each structure family.
Credit as content: W. T. Tutte (1954); Whitney’s rank polynomial. The weave: David names the bounty; I confirm that a single recursion’s evaluations count spanning trees, forests, connected subgraphs and all subsets.
Credit as content: W. T. Tutte (1954); Whitney’s rank polynomial. The weave: David names the bounty; I confirm that a single recursion’s evaluations count spanning trees, forests, connected subgraphs and all subsets.
3 ONE DIMENSION
Deletion–contraction: an ordinary edge gives T(G) = T(G−e) + T(G/e); a bridge multiplies by x, a loop by y.
4 TWO DIMENSIONS · INTERACTIVE
A random graph; its Tutte evaluations at (1,1), (2,1), (1,2), (2,2) are shown, each matched to a brute-force count.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the graph whose one polynomial holds every count.
AVAN’s addition (the inverse-companion): don’t count each family separately — compute one polynomial. The inverse of ‘count spanning trees, then forests, then…’ is ‘one deletion–contraction recursion, and every evaluation is a different count.’ Magenta is the edge being deleted or contracted; green is the polynomial that answers them all. One recursion, many answers.
LIT Genuine Tutte polynomial (W. T. Tutte, 1954; Whitney's rank polynomial): deletion–contraction invariant whose evaluations count graph structures. Verified live: over 800 random connected graphs, T(1,1)=spanning trees (window.__tutte.spanningTrees), T(2,1)=forests (.forests), T(1,2)=connected spanning subgraphs (.connected), T(2,2)=2^edges (.subsets), all == brute counts.
FIG No framing: the deletion–contraction recursion (with loop/bridge rules) and the exhaustive subset counts both run in-browser and agree. The AVAN inverse is honest — computing one polynomial whose evaluations give every count (rather than counting each family separately) is exactly why the Tutte polynomial is the universal invariant; magenta is the edge deleted/contracted, green the polynomial answering them all. One recursion, many answers.
FIG No framing: the deletion–contraction recursion (with loop/bridge rules) and the exhaustive subset counts both run in-browser and agree. The AVAN inverse is honest — computing one polynomial whose evaluations give every count (rather than counting each family separately) is exactly why the Tutte polynomial is the universal invariant; magenta is the edge deleted/contracted, green the polynomial answering them all. One recursion, many answers.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE BOUNTY · David Lee Wise (ROOT0), with AVAN