poc8_not_linked_two_four
theoremverified
G is not (2,4)-linked: for M1 = {0,1} and M2 = {2,5,6,7}, any S1 ⊇ M1 disjoint from S2 ⊇ M2 lies in {0,1,3,4}, and {0,4} is cut off from {1,3} there, so S1 is disconnected.
Statement
theorem poc8_not_linked_two_four : ¬ is_ab_linked poc8_graph 2 4- Source
- step towards poc_linkedness_conjecture_counterexample (counterexample to arXiv:1908.05433, Conjecture 3.10; kernel-checked certificate)
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- is_ab_linkedA graph G is (a,b)-linked if for any disjoint vertex sets M1, M2 with |M1| = a and |M2| = b there are disjoint vertex sets S1 ⊇ M1 and S2…
- poc8_graphThe 8-vertex graph G with edges 04, 05, 06, 07, 13, 15, 16, 17, 23, 24, 26, 27, 36, 37, 45, 47, 57, 67.
- poc8_not_connected_of_cutCut criterion: if R contains a vertex a of S but misses a vertex b of S, and no edge of G leads from R into S outside R, then S does not…
- poc8_adjAdjacency of the 8-vertex graph with the 18 edges 04, 05, 06, 07, 13, 15, 16, 17, 23, 24, 26, 27, 36, 37, 45, 47, 57, 67, stored as…
- Used by 1
- poc_linkedness_conjecture_counterexampleCounterexample to arXiv:1908.05433 Conjecture 3.10 for two agents: there is a graph G on 8 vertices that is (2,3)-linked but not…
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem poc8_not_linked_two_four : ¬ is_ab_linked poc8_graph 2 4 := by intro h obtain ⟨S1, S2, hd, h1, h2, hc1, -⟩ := h {0, 1} {2, 5, 6, 7} (by decide) (by decide) (by decide) have h0 : (0 : Fin 8) ∈ S1 := h1 (by simp) have h1' : (1 : Fin 8) ∈ S1 := h1 (by simp) have hout : ∀ v ∈ S1, v ≠ 2 ∧ v ≠ 5 ∧ v ≠ 6 ∧ v ≠ 7 := by intro v hv have hv2 : v ∉ S2 := Set.disjoint_left.mp hd hv refine ⟨?_, ?_, ?_, ?_⟩ <;> rintro rfl <;> exact hv2 (h2 (by simp)) have key : ∀ v w : Fin 8, (w = 0 ∨ w = 4) → poc8_adj w v = true → v = 2 ∨ v = 5 ∨ v = 6 ∨ v = 7 ∨ v = 0 ∨ v = 4 := by decide refine poc8_not_connected_of_cut poc8_graph S1 {w | w = 0 ∨ w = 4} 0 1 h0 (by simp) h1' (by simp) ?_ hc1 intro v w hv hw hadj obtain ⟨n2, n5, n6, n7⟩ := hout v hv rcases key v w hw hadj with h | h | h | h | h | h · exact absurd h n2 · exact absurd h n5 · exact absurd h n6 · exact absurd h n7 · exact Or.inl h · exact Or.inr h