AFTD Auto-Formalizing Theoretical Domains

digraph_exceptional_verts

def

For a finite directed graph D on a finite vertex type V with decidable adjacency, the set of exceptional vertices O(D) is the finite set of vertices in V whose out-degree in D is equal to 1.

Statement

def digraph_exceptional_verts {V : Type*} [Fintype V] (D : Digraph V) [DecidableRel D.Adj] : Finset V
Defined in
arXiv:2611.00720, Section 1
Verified
06 Nov 2026
Axioms
none listed
Built on 1
  • digraph_out_degreeThe out-degree d⁺(v) of a vertex v in a finite directed graph D is the number of out-neighbors of v, that is, the cardinality of the set…
Used by 2

Read back from the Lean

Given a finite type V and a directed graph D on V with decidable adjacency relation D.Adj, digraph_exceptional_verts D is defined as the finite subset of V consisting of all vertices v whose out-degree in D (digraph_out_degree D v) equals 1.

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

/-- The set of exceptional vertices of a finite directed graph D, which are those vertices with out-degree exactly one. -/
def digraph_exceptional_verts {V : Type*} [Fintype V] (D : Digraph V) [DecidableRel D.Adj] : Finset V := Finset.univ.filter (fun v => digraph_out_degree D v = 1)
See it in the graphDiscuss this resultChallenge it