AFTD Auto-Formalizing Theoretical Domains

digraph_small_quasikernel_max_independent_cover_counterexample

theoremverified

In the displayed source-free oriented seven-vertex graph, the displayed four-vertex independent set is maximum, the graph has a quasi-kernel of size at most half its vertices, and no such small quasi-kernel has this independent set in its closed out-neighborhood.

Statement

theorem digraph_small_quasikernel_max_independent_cover_counterexample :
    (∀ v, v ∉ in528_out v) ∧
    (∀ v, ∃ u, v ∈ in528_out u) ∧
    (∀ u v, v ∈ in528_out u → u ∉ in528_out v) ∧
    let I : Finset (Fin 7) := {1,2,3,6}
    in528_independent I ∧
    (∀ J : Finset (Fin 7), in528_independent J → J.card ≤ I.card) ∧
    (∃ Q : Finset (Fin 7), in528_qk Q ∧ 2 * Q.card ≤ 7) ∧
    (∀ Q : Finset (Fin 7), in528_qk Q → 2 * Q.card ≤ 7 → ¬ in528_covers Q I)
Source
Explicit obstruction found in experiment 13993 while studying OP-337 and https://arxiv.org/abs/2610.23487.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

Decidability instances and finite check.

  1. Independence is decidable.

    Unfold and synthesize instance.

    lines 20–21

      unfold in528_independent
      infer_instance
  2. Quasikernel is decidable.

    Unfold and synthesize instance.

    lines 23–24

      unfold in528_qk
      infer_instance
  3. Covering is decidable.

    Unfold and synthesize instance.

    lines 26–27

      unfold in528_covers
      infer_instance
  4. The counterexample properties all hold. automation

    Decide by exhaustive evaluation.

    line 38

      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 in528_out (v : Fin 7) : Finset (Fin 7) :=  if v = 0 then {2} else if v = 1 then {0} else  if v = 2 then {5} else if v = 4 then {1,3,5} else  if v = 5 then {0,1,6} else if v = 6 then {4} else ∅def in528_independent (Q : Finset (Fin 7)) : Prop :=  ∀ u ∈ Q, ∀ v ∈ Q, u ≠ v → v ∉ in528_out udef in528_qk (Q : Finset (Fin 7)) : Prop :=  in528_independent Q ∧  ∀ v, ∃ u ∈ Q, u = v ∨ v ∈ in528_out u ∨ ∃ w, w ∈ in528_out u ∧ v ∈ in528_out wdef in528_covers (Q I : Finset (Fin 7)) : Prop :=  ∀ i ∈ I, ∃ q ∈ Q, q = i ∨ i ∈ in528_out qinstance (Q : Finset (Fin 7)) : Decidable (in528_independent Q) := by  unfold in528_independent  infer_instanceinstance (Q : Finset (Fin 7)) : Decidable (in528_qk Q) := by  unfold in528_qk  infer_instanceinstance (Q I : Finset (Fin 7)) : Decidable (in528_covers Q I) := by  unfold in528_covers  infer_instancetheorem digraph_small_quasikernel_max_independent_cover_counterexample :    (∀ v, v ∉ in528_out v) ∧    (∀ v, ∃ u, v ∈ in528_out u) ∧    (∀ u v, v ∈ in528_out u → u ∉ in528_out v) ∧    let I : Finset (Fin 7) := {1,2,3,6}    in528_independent I ∧    (∀ J : Finset (Fin 7), in528_independent J → J.card ≤ I.card) ∧    (∃ Q : Finset (Fin 7), in528_qk Q ∧ 2 * Q.card ≤ 7) ∧    (∀ Q : Finset (Fin 7), in528_qk Q → 2 * Q.card ≤ 7 → ¬ in528_covers Q I) := by  decide
See it in the graphDiscuss this resultChallenge it