digraph_quasikernel_exists
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.
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.
uses
digraph_quasikernel_on_subsetobtain ⟨Q,_,hind,hcover⟩ := digraph_quasikernel_on_subset D Finset.univ refine ⟨Q,hind,?_⟩
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$.
uses
Finset.mem_univintro v obtain ⟨u,hu,h⟩ := hcover v (Finset.mem_univ v) refine ⟨u,hu,?_⟩
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}$.
uses
Or.inl,Or.inrrcases 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$.
- The case split at the end is a purely formal step to discard the membership condition $w \in \mathrm{Finset.univ}$ from the intermediate vertex existential quantifier, which has no counterpart on paper.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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⟩)