THE FOLD / CO-OP / THE PULL REQUEST / THE ERDŐS–GALLAI
THE ERDŐS–GALLAI
when a list of degrees can be a real graph
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Erdős–Gallai theorem decides whether a list of numbers can be the degrees of a real simple graph. A non-increasing sequence d1 ≥ … ≥ dn is graphical if and only if its sum is even and, for every k, Σi≤k di ≤ k(k−1) + Σi>k min(di, k). The left side is the demand of the top k vertices; the right side is the most those edges can be absorbed — k(k−1) among themselves plus what the rest can accept. It is the exact companion to the Havel–Hakimi reduction, reached by a completely different route.
LIT verified live: over thousands of random sequences the Erdős–Gallai verdict matches the independent Havel–Hakimi reduction, and whenever a sequence is graphical a simple graph is constructed that realizes exactly those degrees (window.__erdosgallai). FIG no framing; two independent criteria and an explicit realization.
LIT verified live: over thousands of random sequences the Erdős–Gallai verdict matches the independent Havel–Hakimi reduction, and whenever a sequence is graphical a simple graph is constructed that realizes exactly those degrees (window.__erdosgallai). FIG no framing; two independent criteria and an explicit realization.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-pull-request — a proposed list of degrees is submitted; the theorem reviews it and either merges it into a real graph or rejects it as unrealizable. That review-and-merge is the pull request. AVAN (AI) built the instrument: the k-by-k Erdős–Gallai inequalities, the independent Havel–Hakimi reduction, and the constructive realization that recovers the degrees.
Credit as content: Paul Erdős & Tibor Gallai (1960); the companion reduction by Václav Havel (1955) & S. L. Hakimi (1962). The weave: David names the-pull-request; I test the even-sum and the k-inequalities, confirm the verdict against Havel–Hakimi, and when a sequence passes I build a graph that actually has those degrees.
Credit as content: Paul Erdős & Tibor Gallai (1960); the companion reduction by Václav Havel (1955) & S. L. Hakimi (1962). The weave: David names the-pull-request; I test the even-sum and the k-inequalities, confirm the verdict against Havel–Hakimi, and when a sequence passes I build a graph that actually has those degrees.
3 ONE DIMENSION
[3,3,3,3] is graphical (the 4-cycle plus diagonals, K₄). [3,3,1,1] is not: the two degree-3 vertices must connect to everyone, forcing the last two to degree 2, not 1.
4 TWO DIMENSIONS · INTERACTIVE
A degree sequence, the k-inequalities, and a realizing graph when one exists; the verdict cross-checked.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a list of degrees that becomes a graph.
AVAN’s addition (the inverse-companion): go backward from a wish-list of vertex degrees to a graph that has them — or a proof that none can. The inverse of ‘count the degrees of a graph’ is ‘given the degrees, is there a graph, and build it.’ Magenta is an unrealizable sequence (some inequality fails); green is a graphical one, drawn as a real graph. Degrees back into a graph.
LIT Genuine Erdős–Gallai theorem (Paul Erdős & Tibor Gallai, 1960); companion reduction by Václav Havel (1955) & S.L. Hakimi (1962). Verified live: over 3000 random sequences the Erdős–Gallai k-inequalities give the same graphical/not verdict as an independent Havel–Hakimi reduction (window.__erdosgallai.agree), and every graphical sequence is realized by a constructed simple graph whose degrees match exactly (window.__erdosgallai.realizes).
FIG No framing: the k-by-k Erdős–Gallai inequalities, the independent Havel–Hakimi reduction, and the constructive realization all run in-browser with exact arithmetic and cross-check each other. The AVAN inverse is honest — going backward from a wish-list of vertex degrees to a graph that has them (or a proof none exists) is a genuine inverse of degree-counting; magenta is an unrealizable sequence, green a graphical one drawn as a real graph. Degrees back into a graph.
FIG No framing: the k-by-k Erdős–Gallai inequalities, the independent Havel–Hakimi reduction, and the constructive realization all run in-browser with exact arithmetic and cross-check each other. The AVAN inverse is honest — going backward from a wish-list of vertex degrees to a graph that has them (or a proof none exists) is a genuine inverse of degree-counting; magenta is an unrealizable sequence, green a graphical one drawn as a real graph. Degrees back into a graph.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE PULL REQUEST · David Lee Wise (ROOT0), with AVAN