AFTD Auto-Formalizing Theoretical Domains

digraph_is_k_strong

def

A finite digraph D is k-strong (k-strongly connected) if its vertex count exceeds k and for every vertex subset s of cardinality strictly less than k and every distinct pair u, v not in s, there exists a directed path in D from u to v avoiding s.

Statement

def digraph_is_k_strong {V : Type*} [Fintype V] (D : Digraph V) (k : ℕ) : Prop
Defined in
arXiv:2610.36895 Sec. 2
Verified
28 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 8

Read back from the Lean

Given a finite type V (with [Fintype V]), a directed graph D : Digraph V, and a natural number k : ℕ, digraph_is_k_strong D k asserts that: 1. k < Fintype.card V: the cardinality of V is strictly greater than k; and 2. For every finite subset s of V (s : Finset V), if the cardinality of s is strictly less than k (s.card < k), then for all vertices u, v : V, if u ∉ s, v ∉ s, and u ≠ v, there exists a list p : List V such that p is a directed path in D from u to v (as defined by digraph_is_directed_path D p u v) and every vertex x in p satisfies x ∉ s.

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 finite digraph is k-strong if deleting fewer than k vertices leaves a strongly connected digraph. -/
def digraph_is_k_strong {V : Type*} [Fintype V] (D : Digraph V) (k : ℕ) : Prop :=
  k < Fintype.card V ∧
  ∀ (s : Finset V), s.card < k →
    ∀ (u v : V), u ∉ s → v ∉ s → u ≠ v →
      ∃ p : List V, digraph_is_directed_path D p u v ∧ ∀ x ∈ p, x ∉ s
See it in the graphDiscuss this resultChallenge it