AFTD Auto-Formalizing Theoretical Domains

poc8_linked_two_three

theoremverified

The 8-vertex graph G is (2,3)-linked: any 2 terminals and 3 further terminals are separated by a connected bipartition of G.

Statement

theorem poc8_linked_two_three : is_ab_linked poc8_graph 2 3
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 6
  • 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_cover_checkThe cover condition holds for all terminal tuples (x, y, a, b, c).
  • poc8_cover_okCheck for terminals x, y, a, b, c: either they are not distinct, or some stored mask contains x and y and avoids a, b, c.
  • poc8_cands_connEach of the 47 stored masks and its complement pass the Boolean connectivity test (kernel computation).
  • poc8_connb_soundIf the Boolean connectivity test accepts S, then S induces a connected subgraph of G.
  • 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.
Used by 1

Lean source view module on GitHub

theorem poc8_linked_two_three : is_ab_linked poc8_graph 2 3 := by  intro M1 M2 hdisj h1 h2  obtain ⟨x, y, hxy, rfl⟩ := Finset.card_eq_two.mp h1  obtain ⟨a, b, c, hab, hac, hbc, rfl⟩ := Finset.card_eq_three.mp h2  have hxa : x ≠ a := fun h =>    Finset.disjoint_left.mp hdisj (show x ∈ ({x, y} : Finset (Fin 8)) by simp) (by simp [h])  have hxb : x ≠ b := fun h =>    Finset.disjoint_left.mp hdisj (show x ∈ ({x, y} : Finset (Fin 8)) by simp) (by simp [h])  have hxc : x ≠ c := fun h =>    Finset.disjoint_left.mp hdisj (show x ∈ ({x, y} : Finset (Fin 8)) by simp) (by simp [h])  have hya : y ≠ a := fun h =>    Finset.disjoint_left.mp hdisj (show y ∈ ({x, y} : Finset (Fin 8)) by simp) (by simp [h])  have hyb : y ≠ b := fun h =>    Finset.disjoint_left.mp hdisj (show y ∈ ({x, y} : Finset (Fin 8)) by simp) (by simp [h])  have hyc : y ≠ c := fun h =>    Finset.disjoint_left.mp hdisj (show y ∈ ({x, y} : Finset (Fin 8)) by simp) (by simp [h])  have hc := poc8_cover_check x y a b c  have e_hxy : (x == y) = false := by simp [hxy]  have e_hab : (a == b) = false := by simp [hab]  have e_hac : (a == c) = false := by simp [hac]  have e_hbc : (b == c) = false := by simp [hbc]  have e_hxa : (x == a) = false := by simp [hxa]  have e_hxb : (x == b) = false := by simp [hxb]  have e_hxc : (x == c) = false := by simp [hxc]  have e_hya : (y == a) = false := by simp [hya]  have e_hyb : (y == b) = false := by simp [hyb]  have e_hyc : (y == c) = false := by simp [hyc]  unfold poc8_cover_ok at hc  rw [e_hxy, e_hab, e_hac, e_hbc, e_hxa, e_hxb, e_hxc, e_hya, e_hyb, e_hyc] at hc  simp only [Bool.false_or, List.any_eq_true, Bool.and_eq_true, Bool.not_eq_true'] at hc  obtain ⟨m, hm, ⟨⟨⟨⟨hmx, hmy⟩, hma⟩, hmb⟩, hmc⟩⟩ := hc  obtain ⟨hc1, hc2⟩ := poc8_cands_conn m hm  refine ⟨{v | m.testBit v = true}, {v | (!m.testBit v) = true}, ?_, ?_, ?_,    poc8_connb_sound _ hc1, poc8_connb_sound _ hc2⟩  · rw [Set.disjoint_left]    intro v h1 h2    simp only [Set.mem_ofPred_eq] at h1 h2    rw [h1] at h2    exact absurd h2 (by decide)  · intro v hv    simp only [Finset.coe_insert, Finset.coe_singleton, Set.mem_insert_iff,      Set.mem_singleton_iff] at hv    rcases hv with rfl | rfl    · exact hmx    · exact hmy  · intro v hv    simp only [Finset.coe_insert, Finset.coe_singleton, Set.mem_insert_iff,      Set.mem_singleton_iff] at hv    rcases hv with rfl | rfl | rfl    · simp [hma]    · simp [hmb]    · simp [hmc]
See it in the graphDiscuss this resultChallenge it