digraph_seven_tournament_two_neighborhood_cover_counterexample
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.
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.
uses
in528_tournament_qkunfold in528_tournament_qk infer_instance
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).
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
- The proof contains no manual deduction steps; after establishing the decidability instance, Lean's `decide` tactic verifies all seven properties simultaneously by exhaustive finite evaluation.
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.
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