digraph_cyclic_seven_prescribed_neighborhood_counterexample
The displayed eight-vertex graph contains the cyclic seven-tournament, but no quasi-kernel covers the closed out-neighborhood of vertex 0 within that tournament.
Statement
theorem digraph_cyclic_seven_prescribed_neighborhood_counterexample :
(∀ v, v ∉ in541_forced_parent_out v) ∧
(∀ u v : Fin 8, u.val < 7 → v.val < 7 →
(v ∈ in541_forced_parent_out u ↔
(v.val + 7 - u.val) % 7 ∈ ({1,2,4} : Finset ℕ))) ∧
(∀ Q : Finset (Fin 8), in541_forced_parent_qk Q →
¬ (∀ v ∈ ({0,1,2,4} : Finset (Fin 8)),
∃ q ∈ Q, q = v ∨ v ∈ in541_forced_parent_out q))- Source
- Explicit finite counterexample discovered and audited in the cited computations; no novelty is claimed.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
The theorem is proved by finite exhaustive computation using the `decide` tactic. First, the property of being a quasi-kernel is shown to be decidable by expanding its definition into finite quantifications over `Fin 8`. Then, Lean mechanically evaluates the claim across the entire finite graph, checking looplessness, agreement on the first seven vertices with the cyclic tournament $T_7$, and non-coverage of $\{0, 1, 2, 4\}$ by all 256 candidate quasi-kernels.
The property of being a quasi-kernel is decidable for any subset of vertices.
Expanding the definition of `in541_forced_parent_qk` expresses the quasi-kernel property in terms of first-order conditions with bounded universal and existential quantifiers over the finite vertex set `Fin 8` and finite sets of vertices. Since equality, membership, and bounded quantifiers over finite types are decidable, typeclass resolution (`infer_instance`) automatically synthesizes a `Decidable` instance for this proposition.
unfold in541_forced_parent_qk infer_instance
The 8-vertex digraph is loopless, agrees with the cyclic 7-tournament on vertices 0 through 6, and has no quasi-kernel that dominates the closed out-neighborhood of vertex 0. automation
Because all vertex domains and power sets are finite, the entire proposition is decidable. The `decide` tactic checks every condition by exhaustive evaluation: it verifies the lack of self-loops for each of the 8 vertices, checks all pairs among the first 7 vertices to confirm that edge directions match quadratic residues modulo 7 ({1, 2, 4}), and iterates over all 256 subsets of Fin 8, checking that any subset that is a quasi-kernel fails to 1-step dominate {0, 1, 2, 4}.
decide
- The proof relies on Lean's kernel decision procedure `decide` evaluating all 256 candidate subsets of vertices of the 8-element graph by exhaustive computation.
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 in541_forced_parent_out (v : Fin 8) : Finset (Fin 8) := 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 if v = 6 then {0,1,3} else {0}def in541_forced_parent_qk (Q : Finset (Fin 8)) : Prop := (∀ u ∈ Q, ∀ v ∈ Q, u ≠ v → v ∉ in541_forced_parent_out u) ∧ (∀ v, ∃ u ∈ Q, u = v ∨ v ∈ in541_forced_parent_out u ∨ ∃ w, w ∈ in541_forced_parent_out u ∧ v ∈ in541_forced_parent_out w)instance (Q : Finset (Fin 8)) : Decidable (in541_forced_parent_qk Q) := by unfold in541_forced_parent_qk infer_instancetheorem digraph_cyclic_seven_prescribed_neighborhood_counterexample : (∀ v, v ∉ in541_forced_parent_out v) ∧ (∀ u v : Fin 8, u.val < 7 → v.val < 7 → (v ∈ in541_forced_parent_out u ↔ (v.val + 7 - u.val) % 7 ∈ ({1,2,4} : Finset ℕ))) ∧ (∀ Q : Finset (Fin 8), in541_forced_parent_qk Q → ¬ (∀ v ∈ ({0,1,2,4} : Finset (Fin 8)), ∃ q ∈ Q, q = v ∨ v ∈ in541_forced_parent_out q)) := by decide