AFTD Auto-Formalizing Theoretical Domains

digraph_seven_pair_four_cover_counterexample

theoremverified

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.

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

    lines 15–16

    uses in541_pair_four_qk

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

    line 27

      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

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