digraph_seven_cover_counterexample_rigidity
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
- digraph_small_quasikernel_max_independent_cover_counterexampleIn the displayed source-free oriented seven-vertex graph, the displayed four-vertex independent set is maximum, the graph has a…
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.
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.
decide
- The entire proof is executed by computational reflection (`decide`), which checks all 2⁷ = 128 subsets of vertices without generating individual manual proof 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
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.
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