eight_regular_triangle_distinct_certificate
def
A computable boolean certificate checker for the regularity-8 witness problem: it returns true exactly when every one of the n vertices {0,…,n−1} has exactly 8 neighbours in the graph of the edge list L and the vertex triangle-degrees of that graph are pairwise distinct.
Statement
def eight_regular_triangle_distinct_certificate {n : ℕ} (L : List (Fin n × Fin n)) : Bool- Source
- step towards regular_eight_triangle_distinct_witness
- Verified
- 21 Oct 2026
- Axioms
- none listed
- Built on 4
- simple_graph_of_edge_listThe simple graph on {0,…,n−1} whose edges are the unordered pairs occurring in the list L (a pair (a, b) in L contributes the edge {a, b},…
- simple_graph_is_triangle_distinctA graph is triangle-distinct (K_3-irregular) when its vertex triangle-degrees are pairwise distinct.
- simple_graph_of_edge_list_decidable_relAdjacency in the graph determined by an edge list is decidable.
- simple_graph_is_triangle_distinct_decidableFor a finite graph, the proposition that the vertex triangle-degrees are pairwise distinct is decidable.
- Used by 1
- eight_regular_triangle_distinct_of_certificateIf the computable certificate checker accepts the edge list L on the n vertices {0,…,n−1}, then the graph of L is 8-regular and has…
Lean source view module on GitHub
/-- Computable checker: is the graph of this edge list 8-regular with pairwise distinct vertex triangle-degrees? -/ def eight_regular_triangle_distinct_certificate {n : ℕ} (L : List (Fin n × Fin n)) : Bool := ((List.finRange n).all (fun v => ((simple_graph_of_edge_list L).neighborFinset v).card == 8)) && decide (simple_graph_is_triangle_distinct (simple_graph_of_edge_list L))