digraph_source_tournament_quasikernel_singleton
If a nonempty tournament vertex set sends every arc to its complement and receives none, then every quasi-kernel of the whole digraph is a singleton in that tournament.
Statement
theorem digraph_source_tournament_quasikernel_singleton {α : Type} [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (S Q : Finset α) (hS : S.Nonempty) (htour : ∀ u ∈ S, ∀ v ∈ S, u ≠ v → D.Adj u v ∨ D.Adj v u) (hcross : ∀ u ∈ S, ∀ v, v ∉ S → D.Adj u v ∧ ¬ D.Adj v u) (hind : ∀ u ∈ Q, ∀ v ∈ Q, u ≠ v → ¬ D.Adj u v) (hreach : ∀ v, ∃ q ∈ Q, q = v ∨ D.Adj q v ∨ ∃ z, D.Adj q z ∧ D.Adj z v) : ∃ s ∈ S, Q = {s}
- Source
- Elementary block lemma for the explicit counterexample in experiment 14471; no novelty is claimed.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- digraph_nonneighborhood_kernel_no_second_layer_kernel_counterexampleThe displayed source-free oriented twenty-vertex graph has an out-kernel in every non-neighborhood. Its only quasi-kernels are singletons…
The proof, explained
The proof proceeds in three stages. First, the quasi-kernel Q must intersect the source tournament S, because no arcs enter S from its complement, making S unreachable from outside in two steps or fewer. Second, because every vertex in S sends an arc to every vertex outside S, any vertex of Q outside S would receive an arc from the intersection S ∩ Q, contradicting the independence of Q; thus Q ⊆ S. Finally, since S is an induced tournament, any two distinct vertices in S share an arc, forcing the independent set Q to contain at most one vertex and therefore equal {s₀} for some s₀ ∈ S.
The quasi-kernel Q contains at least one vertex of the tournament S.
Assume, for contradiction, that Q does not meet S, so every vertex of S lies outside Q (rewriting the negated existential using not_exists and not_and). Since S is nonempty, pick a vertex s₀ ∈ S. By definition of a quasi-kernel, some q ∈ Q reaches s₀ in at most two steps. Since q ∈ Q, we must have q ∉ S. We analyze the three reachability cases: 1. If q = s₀, this directly contradicts q ∉ S because s₀ ∈ S. 2. If there is an arc q → s₀, this contradicts the cross-arc hypothesis hcross, which says no arc enters S from outside. 3. If there is a two-step path q → z → s₀, we case-split on whether z ∈ S: if z ∈ S, the arc q → z enters S from q ∉ S; if z ∉ S, the arc z → s₀ enters S from z ∉ S. Both subcases contradict hcross. Hence Q must intersect S.
uses
not_exists,not_andclassical -- A quasi-kernel must meet `S`: no vertex outside `S` can reach `S`, not even in two steps. have hmeet : ∃ s ∈ S, s ∈ Q := by obtain ⟨s₀, hs₀⟩ := hS by_contra hcon simp only [not_exists, not_and] at hcon obtain ⟨q, hqQ, hcase⟩ := hreach s₀ have hqS : q ∉ S := fun h => hcon q h hqQ rcases hcase with h | h | ⟨z, hqz, hzs⟩ · exact hqS (h ▸ hs₀) · exact (hcross s₀ hs₀ q hqS).2 h · by_cases hz : z ∈ S · exact (hcross z hz q hqS).2 hqz · exact (hcross s₀ hs₀ z hz).2 hzs
The quasi-kernel Q is entirely contained in S (Q ⊆ S).
Let q ∈ Q, and suppose for contradiction that q ∉ S. Using the vertex s₀ ∈ S ∩ Q obtained in the previous step, s₀ ≠ q since s₀ ∈ S while q ∉ S. By the cross-arc condition hcross, there is a directed arc from s₀ to q. But both s₀ and q belong to the independent set Q, so no arc can exist between them. This contradiction establishes that every element of Q must belong to S.
have hQS : Q ⊆ S := by intro q hq by_contra hqS obtain ⟨s₀, hs₀, hs₀Q⟩ := hmeet have hne : s₀ ≠ q := fun h => hqS (h ▸ hs₀) exact hind s₀ hs₀Q q hq hne (hcross s₀ hs₀ q hqS).1
The quasi-kernel Q is equal to the singleton {s₀} for some s₀ ∈ S.
Fix the vertex s₀ ∈ S ∩ Q found in the first step. To show Q ⊆ {s₀}, consider any q ∈ Q. If q ≠ s₀, then since both s₀ and q belong to S (as Q ⊆ S), the tournament condition htour guarantees an arc between them in one direction or the other: s₀ → q or q → s₀. Either orientation violates the independence of Q, so we must have q = s₀ (using Finset.mem_singleton), proving Q ⊆ {s₀}. Conversely, {s₀} ⊆ Q because s₀ ∈ Q. By subset antisymmetry (Finset.Subset.antisymm), we conclude Q = {s₀}, which proves the theorem with witness s₀ ∈ S.
uses
Finset.mem_singleton,Finset.Subset.antisymmobtain ⟨s₀, hs₀, hs₀Q⟩ := hmeet refine ⟨s₀, hs₀, ?_⟩ have hsub : Q ⊆ {s₀} := by intro q hq simp only [Finset.mem_singleton] by_contra hne have h1 : s₀ ≠ q := fun h => hne h.symm rcases htour s₀ hs₀ q (hQS hq) h1 with h | h · exact hind s₀ hs₀Q q hq h1 h · exact hind q hq s₀ hs₀Q hne h exact Finset.Subset.antisymm hsub (by intro x hx; rw [Finset.mem_singleton] at hx; exact hx ▸ hs₀Q)
not_exists- Negating an existential statement is equivalent to a universal negation: there is no element satisfying a property if and only if all elements fail to satisfy it.
not_and- A conjunction is false if and only if the truth of the first conjunct implies the falsity of the second.
Finset.mem_singleton- An element belongs to a singleton set if and only if it equals the sole element of that set.
Finset.Subset.antisymm- Two finite sets are equal if each is a subset of the other.
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_source_tournament_quasikernel_singleton {α : Type} [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (S Q : Finset α) (hS : S.Nonempty) (htour : ∀ u ∈ S, ∀ v ∈ S, u ≠ v → D.Adj u v ∨ D.Adj v u) (hcross : ∀ u ∈ S, ∀ v, v ∉ S → D.Adj u v ∧ ¬ D.Adj v u) (hind : ∀ u ∈ Q, ∀ v ∈ Q, u ≠ v → ¬ D.Adj u v) (hreach : ∀ v, ∃ q ∈ Q, q = v ∨ D.Adj q v ∨ ∃ z, D.Adj q z ∧ D.Adj z v) : ∃ s ∈ S, Q = {s} := by classical -- A quasi-kernel must meet `S`: no vertex outside `S` can reach `S`, not even in two steps. have hmeet : ∃ s ∈ S, s ∈ Q := by obtain ⟨s₀, hs₀⟩ := hS by_contra hcon simp only [not_exists, not_and] at hcon obtain ⟨q, hqQ, hcase⟩ := hreach s₀ have hqS : q ∉ S := fun h => hcon q h hqQ rcases hcase with h | h | ⟨z, hqz, hzs⟩ · exact hqS (h ▸ hs₀) · exact (hcross s₀ hs₀ q hqS).2 h · by_cases hz : z ∈ S · exact (hcross z hz q hqS).2 hqz · exact (hcross s₀ hs₀ z hz).2 hzs -- Once one member of `S` lies in `Q`, the complete cross-arcs force `Q ⊆ S`. have hQS : Q ⊆ S := by intro q hq by_contra hqS obtain ⟨s₀, hs₀, hs₀Q⟩ := hmeet have hne : s₀ ≠ q := fun h => hqS (h ▸ hs₀) exact hind s₀ hs₀Q q hq hne (hcross s₀ hs₀ q hqS).1 -- Independence inside the tournament `S` leaves at most one vertex. obtain ⟨s₀, hs₀, hs₀Q⟩ := hmeet refine ⟨s₀, hs₀, ?_⟩ have hsub : Q ⊆ {s₀} := by intro q hq simp only [Finset.mem_singleton] by_contra hne have h1 : s₀ ≠ q := fun h => hne h.symm rcases htour s₀ hs₀ q (hQS hq) h1 with h | h · exact hind s₀ hs₀Q q hq h1 h · exact hind q hq s₀ hs₀Q hne h exact Finset.Subset.antisymm hsub (by intro x hx; rw [Finset.mem_singleton] at hx; exact hx ▸ hs₀Q)