AFTD Auto-Formalizing Theoretical Domains

edge_list_connected_cubic_k4

theoremverified

The edge list [(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)] of the complete graph K4 on the vertices 0..3 satisfies edge_list_connected_cubic 4.

Statement

theorem edge_list_connected_cubic_k4 :
    edge_list_connected_cubic 4 [(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)]
Source
Sanity check of edge_list_connected_cubic (K4 is a connected cubic graph), for arXiv:2610.35794 (Computational complexity of the H-coloring problem in cubic graphs)
Verified
30 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • edge_list_connected_cubicTakes n : ℕ and an edge list es : List (ℕ × ℕ), read as a multigraph on the vertices v < n whose edges are the indices i : Fin es.length,…

The proof, explained

The theorem asserts that the edge list of the complete graph K₄ satisfies `edge_list_connected_cubic 4`. The proof splits the definition into its three conjuncts—validity of edge endpoints, degree 3 at every vertex, and graph connectedness—and discharges each subproblem by direct finite computation using `decide`.

  1. The edge list represents a well-formed, 3-regular, connected graph on 4 vertices. automation

    The definition `edge_list_connected_cubic 4 [...]` is a conjunction of three independent properties: (1) every edge consists of two distinct vertices in {0, 1, 2, 3}; (2) each vertex in {0, 1, 2, 3} has degree exactly 3; and (3) the resulting simple graph is connected. The tactic `refine ⟨...⟩` splits the goal into these three subgoals, and each is a finite, decidable combinatorial statement verified directly by computational evaluation (`decide`).

    line 3

      refine ⟨by decide, by decide, by decide⟩

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

theorem edge_list_connected_cubic_k4 :    edge_list_connected_cubic 4 [(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)] := by  refine ⟨by decide, by decide, by decide⟩
See it in the graphDiscuss this resultChallenge it