poc8_not_connected_of_cut
theoremverified
Cut 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 induce a connected subgraph.
Statement
theorem poc8_not_connected_of_cut {V : Type*} (G : SimpleGraph V) (S R : Set V) (a b : V) (ha : a ∈ S) (haR : a ∈ R) (hb : b ∈ S) (hbR : b ∉ R) (hcl : ∀ v w, v ∈ S → w ∈ R → G.Adj w v → v ∈ R) : ¬ is_connected_vertex_set G S
- Source
- step towards poc_linkedness_conjecture_counterexample (counterexample to arXiv:1908.05433, Conjecture 3.10; kernel-checked certificate)
- Verified
- 06 Oct 2026
- Axioms
Quot.soundpropext- Built on 1
- is_connected_vertex_setA vertex set S of a graph G is connected if the subgraph of G induced by S is connected (in particular S is nonempty).
- Used by 2
- poc8_cutb_soundIf the Boolean cut test accepts (S, R), then S does not induce a connected subgraph of G.
- poc8_not_linked_two_fourG 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…
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_connected_of_cut {V : Type*} (G : SimpleGraph V) (S R : Set V) (a b : V) (ha : a ∈ S) (haR : a ∈ R) (hb : b ∈ S) (hbR : b ∉ R) (hcl : ∀ v w, v ∈ S → w ∈ R → G.Adj w v → v ∈ R) : ¬ is_connected_vertex_set G S := by intro hc obtain ⟨p⟩ := hc.preconnected ⟨a, ha⟩ ⟨b, hb⟩ have key : ∀ (x y : S) (q : (G.induce S).Walk x y), (x : V) ∈ R → (y : V) ∈ R := by intro x y q induction q with | nil => exact id | cons h q ih => intro hx; exact ih (hcl _ _ (Subtype.prop _) hx h) exact hbR (key _ _ p haR)