AFTD Auto-Formalizing Theoretical Domains

digraph_has_ckk_subdivision

def

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

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
See it in the graphDiscuss this resultChallenge it