digraph_strict54_nonadj_mask_four
Three pairwise nonadjacent vertices of the nonadjacency masks have no common nonneighbour.
Statement
theorem digraph_strict54_nonadj_mask_four :
∀ a b c : Fin 54, (digraph_strict54_nonadj_mask a.val).testBit b.val = true →
(digraph_strict54_nonadj_mask a.val).testBit c.val = true → (digraph_strict54_nonadj_mask b.val).testBit c.val = true →
(digraph_strict54_nonadj_mask a.val &&& digraph_strict54_nonadj_mask b.val &&& digraph_strict54_nonadj_mask c.val) = 0- Source
- Bitmask certificate for the 54-vertex strictness witness of the weighted center route (IN-522).
- Verified
- 04 Nov 2026
- Axioms
propext- Built on 1
- 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 asserts that in a 54-vertex graph represented by nonadjacency bitmasks, any three pairwise nonadjacent vertices share no common nonneighbour, meaning the graph has no independent set of size four. Because the quantification is over the finite domain Fin 54 and all bitwise operations are computable, the proposition is decidable. The proof proceeds by exhaustive computation checked directly by the Lean kernel.
For every triple of vertices a, b, c ∈ Fin 54, if they are pairwise nonadjacent, their nonadjacency masks share no common bits (their bitwise AND is 0). automation
Because Fin 54 is finite (leaving 54³ = 157,464 triples to consider) and all operations—evaluating the nonadjacency mask, testing bits, and bitwise conjunction—are primitive arithmetic and boolean computations, the goal is a decidable proposition. The `decide +kernel` tactic evaluates the entire exhaustive check directly inside the Lean kernel via computational reflection.
decide +kernel
- The proof contains no manual deduction steps; it is carried out entirely by Lean's kernel exhaustively evaluating all 54³ = 157,464 triples 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_four : ∀ a b c : Fin 54, (digraph_strict54_nonadj_mask a.val).testBit b.val = true → (digraph_strict54_nonadj_mask a.val).testBit c.val = true → (digraph_strict54_nonadj_mask b.val).testBit c.val = true → (digraph_strict54_nonadj_mask a.val &&& digraph_strict54_nonadj_mask b.val &&& digraph_strict54_nonadj_mask c.val) = 0 := by decide +kernel