AFTD Auto-Formalizing Theoretical Domains

digraph_nonneighborhood_kernel_condition_witness

theoremverified

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.

  1. 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.

    lines 14–15

      unfold in541_local_example_independent
      infer_instance
  2. 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.

    line 36

      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

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
See it in the graphDiscuss this resultChallenge it