digraph_strict54_nonadj_mask_sound
Two distinct vertices whose bit is clear in the nonadjacency mask have a common predecessor.
Statement
theorem digraph_strict54_nonadj_mask_sound :
∀ a b : Fin 54, a ≠ b → (digraph_strict54_nonadj_mask a.val).testBit b.val = false →
∃ w : Fin 54, (digraph_strict54_out_mask w.val).testBit a.val = true ∧ (digraph_strict54_out_mask w.val).testBit b.val = true- Source
- Bitmask certificate for the 54-vertex strictness witness of the weighted center route (IN-522).
- Verified
- 04 Nov 2026
- Axioms
Quot.soundpropext- Built on 2
- digraph_strict54_out_maskBit v of the value at u is set exactly when u -> v is an arc of the 54-vertex strictness witness graph.
- digraph_strict54_nonadj_maskBit v of the value at u is set exactly when v differs from u and u, v have no common predecessor in the 54-vertex strictness witness graph.
- Used by 1
- digraph_weighted_center_strict54_certificateThe displayed 54-vertex graph is loopless, oriented, triangle-free and arc-dominated, has minimum outdegree seven and auxiliary…
The proof, explained
The theorem establishes that any two distinct vertices in a 54-vertex directed graph whose nonadjacency mask bit is clear share a common predecessor. Because the vertex set Fin 54 is finite and the mask functions are explicitly defined, the proposition is decidable. The proof proceeds entirely by exhaustive computational verification in the Lean kernel.
For any two distinct vertices a and b in Fin 54, if bit b of the nonadjacency mask of a is false, then there exists a vertex w in Fin 54 that has directed edges to both a and b. automation
The theorem is a purely finite combinatorial statement: the universal quantifiers over a, b ∈ Fin 54 and the existential quantifier over w ∈ Fin 54 range over a finite set of 54 elements, and the masks `digraph_strict54_nonadj_mask` and `digraph_strict54_out_mask` are explicitly computable integer functions. Consequently, the statement has an instance of `Decidable`, and the `decide +kernel` tactic discharges the goal by exhaustive evaluation directly within the Lean kernel.
decide +kernel
- The proof contains no manual deduction steps; it relies entirely on kernel-level evaluation of a decidable finite exhaustive check across all 54 × 54 pairs of vertices.
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_strict54_nonadj_mask_sound : ∀ a b : Fin 54, a ≠ b → (digraph_strict54_nonadj_mask a.val).testBit b.val = false → ∃ w : Fin 54, (digraph_strict54_out_mask w.val).testBit a.val = true ∧ (digraph_strict54_out_mask w.val).testBit b.val = true := by decide +kernel