AFTD Auto-Formalizing Theoretical Domains

digraph_source_tournament_quasikernel_singleton

theoremverified

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

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.

  1. 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.

    lines 9–22

    uses not_exists, not_and

      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
  2. 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.

    lines 24–29

      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
  3. 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.

    lines 31–42

    uses Finset.mem_singleton, Finset.Subset.antisymm

      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)
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

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)
See it in the graphDiscuss this resultChallenge it