digraph_nonneighborhood_kernel_condition_witness
The displayed source-free oriented eight-vertex graph has a singleton kernel in every non-neighborhood and no kernel of its own; it contains a five-clique, and the complement of every tournament vertex set contains a directed triangle.
Statement
theorem digraph_nonneighborhood_kernel_condition_witness :
(∀ v, v ∉ in541_local_example_out v) ∧
(∀ u v, v ∈ in541_local_example_out u → u ∉ in541_local_example_out v) ∧
(∀ v, ∃ u, v ∈ in541_local_example_out u) ∧
(∀ v, ∃ k, k ≠ v ∧ k ∉ in541_local_example_out v ∧
v ∉ in541_local_example_out k ∧
∀ x, x ≠ v → x ∉ in541_local_example_out v →
v ∉ in541_local_example_out x → x = k ∨ x ∈ in541_local_example_out k) ∧
(∀ K : Finset (Fin 8), in541_local_example_independent K →
¬ (∀ v, ∃ u ∈ K, u = v ∨ v ∈ in541_local_example_out u)) ∧
(∀ u ∈ ({1,3,4,5,7} : Finset (Fin 8)),
∀ v ∈ ({1,3,4,5,7} : Finset (Fin 8)), u ≠ v →
v ∈ in541_local_example_out u ∨ u ∈ in541_local_example_out v) ∧
(∀ T : Finset (Fin 8),
(∀ u ∈ T, ∀ v ∈ T, u ≠ v →
v ∈ in541_local_example_out u ∨ u ∈ in541_local_example_out v) →
∃ a b c, a ∉ T ∧ b ∉ T ∧ c ∉ T ∧
b ∈ in541_local_example_out a ∧ c ∈ in541_local_example_out b ∧
a ∈ in541_local_example_out c)- Source
- Finite witness for the non-neighborhood-kernel condition, audited in experiments 14445, 14447 and 14448. No novelty is claimed.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
The proof establishes that an explicit 8-vertex digraph satisfies seven combinatorial properties: it is loopless, oriented, and source-free; every non-neighborhood possesses a singleton kernel; it has no kernel itself; it contains a 5-vertex tournament; and the complement of any tournament sub-digraph contains a directed triangle. The goal is split into these seven claims, each of which is verified by exhaustive finite computation via the decide tactic.
Independence of a vertex set in the digraph is decidable automation
Unfolding the definition of independence expresses it as a bounded universal quantification over the finite set K; typeclass inference synthesizes the decidability instance.
unfold in541_local_example_independent infer_instance
The digraph satisfies all seven stated properties automation
The goal is split into its seven conjuncts, each of which is a finite combinatorial statement over vertices in Fin 8 or subsets in Finset (Fin 8). The decide tactic evaluates and confirms each conjunct by finite exhaustive computation.
refine ⟨?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> decide
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_local_example_out (v : Fin 8) : Finset (Fin 8) := if v = 0 then {4,6} else if v = 1 then {2,3,4} else if v = 2 then {0,5} else if v = 3 then {2,7} else if v = 4 then {3,7} else if v = 5 then {1,3,4,6,7} else if v = 6 then {1,2} else {0,1}def in541_local_example_independent (K : Finset (Fin 8)) : Prop := ∀ u ∈ K, ∀ v ∈ K, u ≠ v → v ∉ in541_local_example_out uinstance (K : Finset (Fin 8)) : Decidable (in541_local_example_independent K) := by unfold in541_local_example_independent infer_instancetheorem digraph_nonneighborhood_kernel_condition_witness : (∀ v, v ∉ in541_local_example_out v) ∧ (∀ u v, v ∈ in541_local_example_out u → u ∉ in541_local_example_out v) ∧ (∀ v, ∃ u, v ∈ in541_local_example_out u) ∧ (∀ v, ∃ k, k ≠ v ∧ k ∉ in541_local_example_out v ∧ v ∉ in541_local_example_out k ∧ ∀ x, x ≠ v → x ∉ in541_local_example_out v → v ∉ in541_local_example_out x → x = k ∨ x ∈ in541_local_example_out k) ∧ (∀ K : Finset (Fin 8), in541_local_example_independent K → ¬ (∀ v, ∃ u ∈ K, u = v ∨ v ∈ in541_local_example_out u)) ∧ (∀ u ∈ ({1,3,4,5,7} : Finset (Fin 8)), ∀ v ∈ ({1,3,4,5,7} : Finset (Fin 8)), u ≠ v → v ∈ in541_local_example_out u ∨ u ∈ in541_local_example_out v) ∧ (∀ T : Finset (Fin 8), (∀ u ∈ T, ∀ v ∈ T, u ≠ v → v ∈ in541_local_example_out u ∨ u ∈ in541_local_example_out v) → ∃ a b c, a ∉ T ∧ b ∉ T ∧ c ∉ T ∧ b ∈ in541_local_example_out a ∧ c ∈ in541_local_example_out b ∧ a ∈ in541_local_example_out c) := by refine ⟨?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> decide