AFTD Auto-Formalizing Theoretical Domains

digraph_seven_cover_counterexample_rigidity

theoremverified

Every independent four-vertex set in the displayed seven-vertex graph equals {1,2,3,6}, and every independent set whose closed out-neighborhood covers {1,2,3,6} also equals it.

Statement

theorem digraph_seven_cover_counterexample_rigidity :
    (∀ J : Finset (Fin 7), in528_independent J → J.card = 4 →
      J = ({1,2,3,6} : Finset (Fin 7))) ∧
    (∀ Q : Finset (Fin 7), in528_independent Q →
      in528_covers Q ({1,2,3,6} : Finset (Fin 7)) →
      Q = ({1,2,3,6} : Finset (Fin 7)))
Source
Seven-vertex graph from experiment 13993; uniqueness audited in experiments 13995 and 14019.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1

The proof, explained

The theorem asserts two uniqueness properties in a specific 7-vertex directed graph: {1, 2, 3, 6} is the only independent set of size 4, and it is the only independent set covering {1, 2, 3, 6}. Since the vertex set has only 7 vertices and all conditions are decidable, the proof proceeds by exhaustive computation over all 2⁷ = 128 candidate subsets via the `decide` tactic.

  1. The subset {1, 2, 3, 6} is the unique 4-element independent set, as well as the unique independent set whose closed out-neighborhood covers {1, 2, 3, 6}. automation

    The vertex set Fin 7 has only 7 elements, meaning there are 2⁷ = 128 subsets in total. Properties such as being an independent set, having cardinality 4, and covering the target set {1, 2, 3, 6} are all algorithmically decidable on finite sets. Lean's `decide` tactic checks the two universally quantified statements by exhaustive enumeration over all subsets.

    line 7

      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

theorem digraph_seven_cover_counterexample_rigidity :    (∀ J : Finset (Fin 7), in528_independent J → J.card = 4 →      J = ({1,2,3,6} : Finset (Fin 7))) ∧    (∀ Q : Finset (Fin 7), in528_independent Q →      in528_covers Q ({1,2,3,6} : Finset (Fin 7)) →      Q = ({1,2,3,6} : Finset (Fin 7))) := by  decide
See it in the graphDiscuss this resultChallenge it