THE FOLD / CO-OP / THE MERGE / THE KÖNIG
THE KÖNIG
a matching and a cover forced to be equal
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
König’s theorem is one of the great min–max dualities: in any bipartite graph, the size of a maximum matching (the most edges you can pick with no shared endpoint) exactly equals the size of a minimum vertex cover (the fewest vertices that touch every edge). Two utterly different optimization problems — one asking for as many pairs as possible, the other for as few guards as possible — always return the same number. And the proof is constructive: from a maximum matching you build the minimum cover directly, by an alternating-path search from the unmatched vertices.
LIT verified live: over 20000 random bipartite graphs, the maximum matching (built by augmenting paths) and the König vertex cover always have equal size, and that cover genuinely touches every edge (window.__konig). FIG no framing; the augmenting-path matching, the alternating-reachability cover, and the covers-every-edge check all run in-browser.
LIT verified live: over 20000 random bipartite graphs, the maximum matching (built by augmenting paths) and the König vertex cover always have equal size, and that cover genuinely touches every edge (window.__konig). FIG no framing; the augmenting-path matching, the alternating-reachability cover, and the covers-every-edge check all run in-browser.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-merge — a matching merges two sides into pairs, and its dual cover is the smallest set of nodes where every merge must pass. Two views of the same join. AVAN (AI) built the instrument: the augmenting-path maximum matching, the alternating-reachability minimum cover, and the equal-size + covers-every-edge checks.
Credit as content: Dénes König (1931); the constructive cover via Egerváry. The weave: David names the merge; I confirm max matching = min cover on every random bipartite graph tested.
Credit as content: Dénes König (1931); the constructive cover via Egerváry. The weave: David names the merge; I confirm max matching = min cover on every random bipartite graph tested.
3 ONE DIMENSION
A bipartite graph: green edges are a maximum matching; ringed vertices are a minimum cover — equal in number.
4 TWO DIMENSIONS · INTERACTIVE
Regenerate the graph; matching size and cover size are computed and compared, and the cover is checked against every edge.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the maximum matching, as many disjoint pairs as possible.
AVAN’s addition (the inverse-companion): don’t maximize pairs — minimize guards. The inverse of ‘the most edges with no shared endpoint’ is ‘the fewest vertices touching every edge’, and König makes the two numbers identical. Magenta is the minimum cover; green is the maximum matching. Two dual extremes, one value.
LIT Genuine König's theorem (Dénes König, 1931; constructive cover via Egerváry). Verified live: over 20000 random bipartite graphs the maximum matching (augmenting paths) and the minimum vertex cover (alternating-reachability construction) always have equal size, and the cover touches every edge (window.__konig.sizeMatches, .coversAll).
FIG No framing; the augmenting-path matching, the alternating-reachability cover, and the covers-every-edge check all run in-browser. The AVAN inverse is honest — instead of maximizing disjoint pairs, minimize the vertices touching every edge; König forces the two numbers identical. Magenta is the minimum cover; green is the maximum matching. Two dual extremes, one value.
FIG No framing; the augmenting-path matching, the alternating-reachability cover, and the covers-every-edge check all run in-browser. The AVAN inverse is honest — instead of maximizing disjoint pairs, minimize the vertices touching every edge; König forces the two numbers identical. Magenta is the minimum cover; green is the maximum matching. Two dual extremes, one value.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE MERGE · David Lee Wise (ROOT0), with AVAN