AFTD Auto-Formalizing Theoretical Domains

digraph_seven_tournament_two_neighborhood_cover_counterexample

theoremverified

The displayed source-free seven-vertex tournament has all singleton quasi-kernels, every quasi-kernel is a singleton, no pair of their closed out-neighborhoods covers all vertices, and each vertex belongs to four of those neighborhoods.

Statement

theorem digraph_seven_tournament_two_neighborhood_cover_counterexample :
    (∀ v, v ∉ in528_tournament_out v) ∧
    (∀ v, ∃ u, v ∈ in528_tournament_out u) ∧
    (∀ u v, u ≠ v → (v ∈ in528_tournament_out u ∨ u ∈ in528_tournament_out v)) ∧
    (∀ v, in528_tournament_qk {v}) ∧
    (∀ Q : Finset (Fin 7), in528_tournament_qk Q → ∃ v, Q = {v}) ∧
    (∀ u v : Fin 7, ∃ z : Fin 7,
      z ≠ u ∧ z ∉ in528_tournament_out u ∧ z ≠ v ∧ z ∉ in528_tournament_out v) ∧
    (∀ z : Fin 7,
      (Finset.univ.filter fun u => u = z ∨ z ∈ in528_tournament_out u).card = 4)
Source
Classical cyclic tournament, https://www.combinatorics.org/ojs/index.php/eljc/article/download/v13i1r69/pdf/; the two-cover obstruction was audited in experiment 13998.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

The theorem proves seven structural properties of a specific source-free 7-vertex tournament (the Paley tournament of order 7) via computational exhaustion. First, decidability of the quasi-kernel predicate is established by unfolding its definition into a first-order formula over the finite type Fin 7, which typeclass resolution resolves. The `decide` tactic then evaluates the entire conjunction by exhaustive enumeration over the 7 vertices and 128 vertex subsets, verifying that all singletons and only singletons are quasi-kernels, no two closed out-neighborhoods cover the tournament, and each vertex belongs to exactly four closed out-neighborhoods.

  1. The quasi-kernel property for any vertex subset Q ⊆ Fin 7 is decidable. automation

    Unfolding `in528_tournament_qk` reduces the predicate to a bounded first-order formula over the finite type Fin 7, asserting that Q is independent and reaches every vertex in at most two steps. Since Fin 7 is finite with decidable equality, typeclass synthesis (`infer_instance`) automatically constructs the decision procedure.

    lines 14–15

    uses in528_tournament_qk

      unfold in528_tournament_qk
      infer_instance
  2. The seven-vertex tournament is loopless, source-free, and complete; its quasi-kernels are precisely the seven singletons; no pair of closed out-neighborhoods covers the vertex set; and each vertex belongs to exactly four closed out-neighborhoods. automation

    Since Fin 7 has 7 vertices and only 2^7 = 128 subsets, the entire seven-part conjunction consists of decidable statements over finite domains. The `decide` tactic evaluates the goal by exhaustive computation, verifying that: (1) no vertex has a self-loop; (2) every vertex has in-degree at least 1; (3) every distinct pair has a directed edge; (4) each singleton {v} is a quasi-kernel; (5) no other subset is a quasi-kernel; (6) any pair of closed out-neighborhoods N⁺[u] ∪ N⁺[v] leaves at least one vertex uncovered; and (7) each vertex belongs to the closed out-neighborhoods of exactly 4 vertices (itself and its 3 in-neighbors).

    line 27

      decide
in528_tournament_qk
the proposition that a vertex subset Q in Fin 7 is a quasi-kernel: Q is independent, and every vertex is reachable from Q in at most two steps

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

set_option maxRecDepth 50000set_option maxHeartbeats 50000000def in528_tournament_out (v : Fin 7) : Finset (Fin 7) :=  if v = 0 then {1,2,4} else if v = 1 then {2,3,5} else  if v = 2 then {3,4,6} else if v = 3 then {0,4,5} else  if v = 4 then {1,5,6} else if v = 5 then {0,2,6} else {0,1,3}def in528_tournament_qk (Q : Finset (Fin 7)) : Prop :=  (∀ u ∈ Q, ∀ v ∈ Q, u ≠ v → v ∉ in528_tournament_out u) ∧  (∀ v, ∃ u ∈ Q, u = v ∨ v ∈ in528_tournament_out u ∨    ∃ w, w ∈ in528_tournament_out u ∧ v ∈ in528_tournament_out w)instance (Q : Finset (Fin 7)) : Decidable (in528_tournament_qk Q) := by  unfold in528_tournament_qk  infer_instancetheorem digraph_seven_tournament_two_neighborhood_cover_counterexample :    (∀ v, v ∉ in528_tournament_out v) ∧    (∀ v, ∃ u, v ∈ in528_tournament_out u) ∧    (∀ u v, u ≠ v → (v ∈ in528_tournament_out u ∨ u ∈ in528_tournament_out v)) ∧    (∀ v, in528_tournament_qk {v}) ∧    (∀ Q : Finset (Fin 7), in528_tournament_qk Q → ∃ v, Q = {v}) ∧    (∀ u v : Fin 7, ∃ z : Fin 7,      z ≠ u ∧ z ∉ in528_tournament_out u ∧ z ≠ v ∧ z ∉ in528_tournament_out v) ∧    (∀ z : Fin 7,      (Finset.univ.filter fun u => u = z ∨ z ∈ in528_tournament_out u).card = 4) := by  decide
See it in the graphDiscuss this resultChallenge it