AFTD Auto-Formalizing Theoretical Domains

digraph_exceptional_verts_card_le

theoremverified

For any finite directed graph D on a finite vertex type V with decidable adjacency, the number of exceptional vertices (vertices of out-degree 1) in D is at most the cardinality of V.

Statement

theorem digraph_exceptional_verts_card_le {V : Type*} [Fintype V] (D : Digraph V) [DecidableRel D.Adj] : (digraph_exceptional_verts D).card ≤ Fintype.card V
Source
folklore
Verified
06 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • digraph_exceptional_vertsFor 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…
  • 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…

Read back from the Lean

For any finite type V and any directed graph D on V with a decidable adjacency relation, the number of vertices with out-degree equal to 1 is less than or equal to the total number of vertices in V (Fintype.card V).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The set of exceptional vertices is a subset of the finite vertex type V. The theorem follows directly by applying the standard fact that any finite subset of a finite type has cardinality bounded by the cardinality of the type (Finset.card_le_univ).

  1. The number of exceptional vertices is at most the cardinality of V.

    Since the set of exceptional vertices `digraph_exceptional_verts D` is defined as a finite subset of `V`, its cardinality is at most the total number of elements in `V` by `Finset.card_le_univ`.

    line 2

    uses Finset.card_le_univ

    theorem digraph_exceptional_verts_card_le {V : Type*} [Fintype V] (D : Digraph V) [DecidableRel D.Adj] : (digraph_exceptional_verts D).card ≤ Fintype.card V := Finset.card_le_univ _
Finset.card_le_univ
The cardinality of any finite subset of a finite type is at most the total cardinality of the type.

Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- The number of exceptional vertices in a finite digraph D on V is at most the total number of vertices |V|. -/theorem digraph_exceptional_verts_card_le {V : Type*} [Fintype V] (D : Digraph V) [DecidableRel D.Adj] : (digraph_exceptional_verts D).card ≤ Fintype.card V := Finset.card_le_univ _
See it in the graphDiscuss this resultChallenge it