eight_regular_triangle_distinct_of_certificate
If 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 pairwise distinct vertex triangle-degrees. Consequently any accepted list is, on its own, a proof that the existential regularity-8 witness statement holds at that order.
Statement
theorem eight_regular_triangle_distinct_of_certificate {n : ℕ} (L : List (Fin n × Fin n))
(h : eight_regular_triangle_distinct_certificate L = true) :
(simple_graph_of_edge_list L).IsRegularOfDegree 8 ∧
simple_graph_is_triangle_distinct (simple_graph_of_edge_list L)- Source
- step towards regular_eight_triangle_distinct_witness
- Verified
- 22 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- eight_regular_triangle_distinct_certificateA computable boolean certificate checker for the regularity-8 witness problem: it returns true exactly when every one of the n vertices…
- simple_graph_regular_of_degree_iff_neighbor_cardA finite simple graph is regular of degree d if and only if every vertex has exactly d neighbours, counted as the cardinality of its…
- simple_graph_is_triangle_distinct_decidableFor a finite graph, the proposition that the vertex triangle-degrees are pairwise distinct is decidable.
- simple_graph_is_triangle_distinctA graph is triangle-distinct (K_3-irregular) when its vertex triangle-degrees are pairwise distinct.
- 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_of_edge_list_decidable_relAdjacency in the graph determined by an edge list is decidable.
The proof, explained
The certificate checker evaluates a boolean conjunction of two tests: an exhaustive check that every vertex has degree 8, and a decision procedure verifying that the triangle-degrees of all vertices are pairwise distinct. The proof unfolds the certificate definition and separates the assumption into these two components. It discharges the triangle-distinctness goal directly via boolean reflection using `of_decide_eq_true`. Finally, it reduces 8-regularity to showing that every vertex has degree 8, which holds because every vertex belongs to `List.finRange n` and therefore passed the certificate's degree check.
The certificate hypothesis decomposes into two conditions: every vertex satisfies the degree check, and the triangle-degree distinctness decision evaluates to true.
Unfolding the definition of `eight_regular_triangle_distinct_certificate`, the assumption `h` is a boolean conjunction `A && B = true`. By `Bool.and_eq_true`, this is equivalent to two separate facts: the exhaustive degree check over all vertices in `List.finRange n` is true (`h1`), and the decidable check for distinct triangle-degrees is true (`h2`).
uses
Bool.and_eq_truerw [eight_regular_triangle_distinct_certificate, Bool.and_eq_true] at h obtain ⟨h1, h2⟩ := h
The graph has pairwise distinct vertex triangle-degrees, reducing the goal to establishing 8-regularity.
The theorem goal is a conjunction of 8-regularity and triangle-degree distinctness. By `of_decide_eq_true`, the second certificate fact `h2` directly proves that `simple_graph_is_triangle_distinct` holds for the graph, leaving only the 8-regularity claim.
uses
of_decide_eq_truerefine ⟨?_, of_decide_eq_true h2⟩The graph is 8-regular.
By `simple_graph_regular_of_degree_iff_neighbor_card`, 8-regularity is equivalent to every vertex having degree 8. For an arbitrary vertex `v`, since `v` belongs to `List.finRange n` by `List.mem_finRange`, the certificate's degree test `h1` implies via `List.all_eq_true.mp` that the check `card == 8` evaluates to true for `v`. Simplifying this boolean equality shows the neighborhood of `v` has cardinality 8, completing the proof.
uses
simple_graph_regular_of_degree_iff_neighbor_card,List.all_eq_true.mp,List.mem_finRangerw [simple_graph_regular_of_degree_iff_neighbor_card] intro v have := (List.all_eq_true.mp h1) v (List.mem_finRange v) simpa using this
Bool.and_eq_true- A boolean conjunction `a && b` is true if and only if both `a = true` and `b = true`.
of_decide_eq_true- If the boolean decision `decide p` of a decidable proposition `p` evaluates to `true`, then `p` holds.
simple_graph_regular_of_degree_iff_neighbor_card- A simple graph is regular of degree `d` if and only if every vertex has neighbor finset of cardinality `d`.
List.all_eq_true.mp- If `List.all` evaluates to `true` on a list, then the boolean predicate holds for every element in the list.
List.mem_finRange- Every index `x : Fin n` belongs to `List.finRange n`.
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.
/-- Soundness of the computable certificate checker: a true check yields an 8-regular triangle-distinct graph. -/theorem eight_regular_triangle_distinct_of_certificate {n : ℕ} (L : List (Fin n × Fin n)) (h : eight_regular_triangle_distinct_certificate L = true) : (simple_graph_of_edge_list L).IsRegularOfDegree 8 ∧ simple_graph_is_triangle_distinct (simple_graph_of_edge_list L) := by rw [eight_regular_triangle_distinct_certificate, Bool.and_eq_true] at h obtain ⟨h1, h2⟩ := h refine ⟨?_, of_decide_eq_true h2⟩ rw [simple_graph_regular_of_degree_iff_neighbor_card] intro v have := (List.all_eq_true.mp h1) v (List.mem_finRange v) simpa using this