AFTD Auto-Formalizing Theoretical Domains

digraph_quasikernel_exists

theoremverified

Every finite digraph contains an independent set from which every vertex is reachable in at most two directed arcs.

Statement

theorem digraph_quasikernel_exists
    {α : Type} [Fintype α] [DecidableEq α]
    (D : Digraph α) [DecidableRel D.Adj] :
    ∃ Q : Finset α,
      (∀ u ∈ Q, ∀ v ∈ Q, u ≠ v → ¬ D.Adj u v) ∧
      (∀ v, ∃ u ∈ Q, u = v ∨ D.Adj u v ∨ ∃ w, D.Adj u w ∧ D.Adj w v)
Source
Standard qualitative quasi-kernel existence construction, recalled in arXiv:2601.11847 Section 1.1; foundational helper for OP-337.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • digraph_quasikernel_on_subsetFor any finite digraph and any finite vertex subset S there is an independent Q contained in S such that every vertex of S is reachable…

The proof, explained

The theorem states Chvátal's conjecture / the quasi-kernel theorem for finite digraphs: every finite directed graph has an independent set (a quasi-kernel) from which every vertex is reachable by a path of length at most 2. The proof specializes the general lemma `digraph_quasikernel_on_subset` to the full vertex set `Finset.univ`, which immediately yields an independent set $Q$ that 2-dominates all vertices. The remaining steps simply instantiate this covering property for an arbitrary vertex $v$ and unpack the cases to eliminate the universe-membership condition on the intermediate vertex.

  1. There exists an independent set $Q$ such that it suffices to show every vertex is reachable from $Q$ in at most two steps.

    We apply the helper theorem `digraph_quasikernel_on_subset` to the universal set of all vertices, `Finset.univ`. This provides a set $Q \subseteq \mathrm{Finset.univ}$ that is independent (`hind`) and 2-step dominating for all vertices in the universe (`hcover`). Providing $Q$ as the witness and supplying its independence proof `hind`, the remaining goal is to show that every vertex in the digraph is reachable from $Q$ in at most two steps.

    lines 7–8

    uses digraph_quasikernel_on_subset

      obtain ⟨Q,_,hind,hcover⟩ := digraph_quasikernel_on_subset D Finset.univ
      refine ⟨Q,hind,?_⟩
  2. For any vertex $v$, there exists a vertex $u \in Q$ that reaches $v$ in at most two steps.

    Let $v$ be an arbitrary vertex. Since $v \in \mathrm{Finset.univ}$ by `Finset.mem_univ`, the covering property `hcover` yields a vertex $u \in Q$ such that either $u = v$, $u \to v$, or $u \to w \to v$ for some $w \in \mathrm{Finset.univ}$. Choosing $u$ and its membership proof `hu`, we are left to show that this reachability condition implies reachability without the set restriction on $w$.

    lines 9–11

    uses Finset.mem_univ

      intro v
      obtain ⟨u,hu,h⟩ := hcover v (Finset.mem_univ v)
      refine ⟨u,hu,?_⟩
  3. The reachability condition holds for $u$ and $v$.

    We unpack the disjunction $h$: if $u = v$, the claim holds by the first disjunct (`Or.inl`); if $u \to v$, it holds by the second disjunct (`Or.inr (Or.inl ...)`); and if there is a two-step path $u \to w \to v$ with $w \in \mathrm{Finset.univ}$, we provide $w$ as the witness to satisfy the third disjunct (`Or.inr (Or.inr ...)`), discarding the redundant membership hypothesis $w \in \mathrm{Finset.univ}$.

    lines 12–15

    uses Or.inl, Or.inr

      rcases h with heq | hadj | ⟨w,_,huw,hwv⟩
      · exact Or.inl heq
      · exact Or.inr (Or.inl hadj)
      · exact Or.inr (Or.inr ⟨w,huw,hwv⟩)
digraph_quasikernel_on_subset
Every subset $S$ of vertices in a finite digraph contains an independent set $Q \subseteq S$ from which every vertex in $S$ can be reached in at most two directed arcs within $S$.
Finset.mem_univ
Every element of a finite type belongs to the universal finite set `Finset.univ`.
Or.inl
Left injection for a disjunction: from $A$, infer $A \lor B$.
Or.inr
Right injection for a disjunction: from $B$, infer $A \lor B$.

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

theorem digraph_quasikernel_exists    {α : Type} [Fintype α] [DecidableEq α]    (D : Digraph α) [DecidableRel D.Adj] :    ∃ Q : Finset α,      (∀ u ∈ Q, ∀ v ∈ Q, u ≠ v → ¬ D.Adj u v) ∧      (∀ v, ∃ u ∈ Q, u = v ∨ D.Adj u v ∨ ∃ w, D.Adj u w ∧ D.Adj w v) := by  obtain ⟨Q,_,hind,hcover⟩ := digraph_quasikernel_on_subset D Finset.univ  refine ⟨Q,hind,?_⟩  intro v  obtain ⟨u,hu,h⟩ := hcover v (Finset.mem_univ v)  refine ⟨u,hu,?_⟩  rcases h with heq | hadj | ⟨w,_,huw,hwv⟩  · exact Or.inl heq  · exact Or.inr (Or.inl hadj)  · exact Or.inr (Or.inr ⟨w,huw,hwv⟩)
See it in the graphDiscuss this resultChallenge it