edge_list_connected_cubic_k4
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`.
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`).
refine ⟨by decide, by decide, by decide⟩
- All three subgoals (valid endpoints, 3-regularity, and connectedness) are verified by Lean's computational decision procedure `decide` rather than by manual deductive steps.
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 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⟩