AFTD Auto-Formalizing Theoretical Domains

digraph_is_quasi_kernel_empty_of_isEmpty

theoremverified

In an empty digraph, the empty set is a quasi-kernel.

Statement

theorem digraph_is_quasi_kernel_empty_of_isEmpty {α : Type*} [IsEmpty α] (D : Digraph α) :
    digraph_is_quasi_kernel D ∅
Source
step towards digraph_small_quasi_kernel_exists
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • digraph_is_quasi_kernelA subset Q of vertices in a digraph D is a quasi-kernel if Q is independent (no arcs between distinct vertices of Q) and 2-dominating…
  • digraph_reverse_reverseReversing a digraph twice yields the original digraph.
Used by 1

The proof, explained

In an empty digraph (where the vertex type is empty), the empty set of vertices is vacuously a quasi-kernel. Unfolding the definition gives an independence condition on vertices in ∅ and a reachability condition for all vertices in the graph, both of which are vacuously true because there are no vertices. The simplifier recognizes these vacuous truths and closes the goal.

  1. The empty set ∅ is a quasi-kernel of any digraph D on an empty vertex type. automation

    Unfolding the definition of a quasi-kernel (`digraph_is_quasi_kernel`) requires verifying two conditions: independence of the subset, and that every vertex in the graph is reachable from the subset in at most two steps. Because the subset is ∅, the independence condition is vacuously satisfied. Because the vertex type α is empty (`IsEmpty α`), the reachability condition for all vertices is also vacuously satisfied. The automated simplifier `simpa` reduces both conditions to true.

    line 3

    uses digraph_is_quasi_kernel, digraph_reverse_reverse

        digraph_is_quasi_kernel D ∅ := by first | exact digraph_reverse_reverse | (apply digraph_reverse_reverse <;> assumption) | (apply digraph_reverse_reverse <;> simp_all) | simpa using digraph_reverse_reverse | (simp only [digraph_is_quasi_kernel] at *; first | exact digraph_reverse_reverse | (apply digraph_reverse_reverse <;> assumption) | (apply digraph_reverse_reverse <;> simp_all) | simpa using digraph_reverse_reverse)
digraph_is_quasi_kernel
a subset Q of vertices in a digraph is a quasi-kernel if it is independent (no two vertices in Q are adjacent) and every vertex in the graph is reachable from some vertex in Q in at most two steps
digraph_reverse_reverse
reversing all edges of a directed graph twice yields the original digraph

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- The empty set of vertices is a quasi-kernel in any empty digraph. -/theorem digraph_is_quasi_kernel_empty_of_isEmpty {α : Type*} [IsEmpty α] (D : Digraph α) :    digraph_is_quasi_kernel D ∅ := by first | exact digraph_reverse_reverse | (apply digraph_reverse_reverse <;> assumption) | (apply digraph_reverse_reverse <;> simp_all) | simpa using digraph_reverse_reverse | (simp only [digraph_is_quasi_kernel] at *; first | exact digraph_reverse_reverse | (apply digraph_reverse_reverse <;> assumption) | (apply digraph_reverse_reverse <;> simp_all) | simpa using digraph_reverse_reverse)
See it in the graphDiscuss this resultChallenge it