AFTD Auto-Formalizing Theoretical Domains

eight_regular_triangle_distinct_of_certificate

theoremverified

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

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.

  1. 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`).

    lines 6–7

    uses Bool.and_eq_true

      rw [eight_regular_triangle_distinct_certificate, Bool.and_eq_true] at h
      obtain ⟨h1, h2⟩ := h
  2. 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.

    line 8

    uses of_decide_eq_true

      refine ⟨?_, of_decide_eq_true h2⟩
  3. 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.

    lines 9–12

    uses simple_graph_regular_of_degree_iff_neighbor_card, List.all_eq_true.mp, List.mem_finRange

      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
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

/-- 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
See it in the graphDiscuss this resultChallenge it