digraph_seven_pair_four_cover_counterexample
The displayed source-free oriented seven-vertex graph has no quasi-kernel whose closed out-neighborhood contains both vertices 0 and 1 and at least four vertices.
Statement
theorem digraph_seven_pair_four_cover_counterexample : (∀ v, v ∉ in541_pair_four_out v) ∧ (∀ v, ∃ u, v ∈ in541_pair_four_out u) ∧ (∀ u v, v ∈ in541_pair_four_out u → u ∉ in541_pair_four_out v) ∧ (∀ Q : Finset (Fin 7), in541_pair_four_qk Q → (∃ q ∈ Q, q = 0 ∨ (0 : Fin 7) ∈ in541_pair_four_out q) → (∃ q ∈ Q, q = 1 ∨ (1 : Fin 7) ∈ in541_pair_four_out q) → (Finset.univ.filter fun v => ∃ q ∈ Q, q = v ∨ v ∈ in541_pair_four_out q).card < 4)
- 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 verified by finite exhaustive computation. An auxiliary instance first establishes that the quasi-kernel property is decidable for every vertex subset of the 7-vertex digraph. The main statement—asserting that the digraph is loopless, source-free, and oriented, and that no quasi-kernel covering both vertices 0 and 1 has a closed out-neighborhood containing four or more vertices—is then verified directly by the `decide` tactic over all 128 vertex subsets.
For every subset Q of vertices in the 7-vertex digraph, the condition that Q is a quasi-kernel is decidable.
We unfold the definition of `in541_pair_four_qk`. A subset Q is a quasi-kernel if it is independent (no directed edge between distinct vertices of Q) and every vertex in the graph is reachable from Q in at most two steps. Because the vertex set Fin 7 and the subset Q are finite, all universal and existential quantifiers are bounded over finite sets. Since equality and edge membership are also decidable, typeclass synthesis (`infer_instance`) automatically derives the decidability of the property.
uses
in541_pair_four_qkunfold in541_pair_four_qk infer_instance
The digraph is loopless, source-free, and oriented, and every quasi-kernel whose closed out-neighborhood contains both 0 and 1 has a closed out-neighborhood of size strictly less than 4.
With decidability established for the quasi-kernel property and all edge conditions, the four conjuncts of the theorem consist purely of bounded quantifiers over the 7-element vertex type Fin 7 and its power set of 128 candidate subsets Q. The `decide` tactic checks each condition by exhaustive finite evaluation, closing the goal.
decide
in541_pair_four_qk- the predicate stating that a subset Q of vertices is a quasi-kernel, i.e., an independent set such that every vertex in the digraph is reachable from Q in at most two steps
- The proof relies entirely on Lean's computational evaluation (`decide`); all digraph properties and the non-existence of a quasi-kernel covering vertices 0 and 1 with closed out-neighborhood size at least 4 are verified by exhaustive enumeration over Fin 7 and its 128 subsets.
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_pair_four_out (v : Fin 7) : Finset (Fin 7) := if v = 0 then {2,4,5,6} else if v = 1 then {0,3} else if v = 2 then {1} else if v = 3 then {6} else if v = 4 then {1,3,5} else if v = 5 then {1,6} else {1,2}def in541_pair_four_qk (Q : Finset (Fin 7)) : Prop := (∀ u ∈ Q, ∀ v ∈ Q, u ≠ v → v ∉ in541_pair_four_out u) ∧ (∀ v, ∃ u ∈ Q, u = v ∨ v ∈ in541_pair_four_out u ∨ ∃ w, w ∈ in541_pair_four_out u ∧ v ∈ in541_pair_four_out w)instance (Q : Finset (Fin 7)) : Decidable (in541_pair_four_qk Q) := by unfold in541_pair_four_qk infer_instancetheorem digraph_seven_pair_four_cover_counterexample : (∀ v, v ∉ in541_pair_four_out v) ∧ (∀ v, ∃ u, v ∈ in541_pair_four_out u) ∧ (∀ u v, v ∈ in541_pair_four_out u → u ∉ in541_pair_four_out v) ∧ (∀ Q : Finset (Fin 7), in541_pair_four_qk Q → (∃ q ∈ Q, q = 0 ∨ (0 : Fin 7) ∈ in541_pair_four_out q) → (∃ q ∈ Q, q = 1 ∨ (1 : Fin 7) ∈ in541_pair_four_out q) → (Finset.univ.filter fun v => ∃ q ∈ Q, q = v ∨ v ∈ in541_pair_four_out q).card < 4) := by decide