digraph_is_k_strong
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
- digraph_four_strong_tournament_unilaterally_two_linkedLet D be a digraph on a finite type V. If D is a tournament and D is 4-strong, then D is unilaterally 2-linked.
- linkage_of_common_neighborIn a 4-strong digraph D, if v is outside {s₁, t₁, s₂, t₂} and (s₁ → v → t₁) or (t₁ → v → s₁), then unilateral 2-linkage exists for {s₁,…
- digraph_five_strong_short_path_avoiding_finsetLet D be 5-strong, A₀ a set of at most 2 vertices and T a set of fewer than 3 vertices. Then any two distinct vertices outside T ∪ A₀ are…
- digraph_four_strong_semicomplete_multipartite_adjacent_pair_linkedLet D be a 4-strong semicomplete multipartite digraph on a finite type V. If s₁, t₁, s₂, t₂ are pairwise distinct vertices of D such that…
- digraph_exists_four_strong_semicomplete_multipartite_not_unilaterally_two_linked_eightThere exists a finite type V with exactly 8 elements and a digraph D on V such that D is 4-strong, semicomplete multipartite, and not…
- digraph_four_strong_semicomplete_multipartite_adjacent_pair_linked_rightLet D be a 4-strong semicomplete multipartite digraph. If s₁, t₁, s₂, t₂ are pairwise distinct vertices such that there is an arc between…
- short_path_gives_linkage_four_strongIn a 4-strong digraph D, if there is a directed path between {s₁, t₁} with at most 3 vertices that avoids {s₂, t₂}, then there exist…
- linkage_of_common_neighbor_rightIn a 4-strong digraph D, if v is outside {s₁, t₁, s₂, t₂} and (s₂ → v → t₂) or (t₂ → v → s₂), then unilateral 2-linkage exists for {s₁,…
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