digraph_has_ckk_subdivision
A digraph D contains a subdivision of C(k,k) if there exist two distinct vertices u, v and two internally vertex-disjoint directed paths from u to v, each having length at least k (at least k+1 vertices).
Statement
def digraph_has_ckk_subdivision {V : Type*} (D : Digraph V) (k : ℕ) : Prop
- Defined in
- arXiv:2610.38574 Section 1 & Section 2.1
- Verified
- 30 Oct 2026
- Axioms
- none listed
- Built on 1
- digraph_is_directed_pathA directed path from u to v in a digraph D is a list of vertices p forming a directed chain in D with no duplicate vertices, starting at u…
- Used by 1
- not_digraph_ckk_subdivision_three_exceptionalThe statement
digraph_ckk_subdivision_three_exceptionalis false: The statement omits any nonemptiness hypothesis on the vertex type, so…
- not_digraph_ckk_subdivision_three_exceptionalThe statement
Read back from the Lean
For a directed graph D on vertex type V and a natural number k, digraph_has_ckk_subdivision D k asserts that there exist distinct vertices u, v : V and lists of vertices p₁, p₂ : List V such that:
1. p₁ is a directed path in D from u to v (consecutive elements satisfy D.Adj, elements are pairwise distinct, p₁ begins with u, and ends with v),
2. p₂ is a directed path in D from u to v,
3. p₁ has at least k + 1 vertices (k + 1 ≤ p₁.length),
4. p₂ has at least k + 1 vertices (k + 1 ≤ p₂.length), and
5. p₁ and p₂ are internally vertex-disjoint, meaning any vertex w present in both p₁ and p₂ must be either u or v.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- A digraph D contains a subdivision of C(k,k) if it has two internally vertex-disjoint directed paths between distinct vertices, each of length at least k. -/ def digraph_has_ckk_subdivision {V : Type*} (D : Digraph V) (k : ℕ) : Prop := ∃ (u v : V) (p₁ p₂ : List V), u ≠ v ∧ digraph_is_directed_path D p₁ u v ∧ digraph_is_directed_path D p₂ u v ∧ k + 1 ≤ p₁.length ∧ k + 1 ≤ p₂.length ∧ ∀ w : V, w ∈ p₁ → w ∈ p₂ → w = u ∨ w = v