edge_list_connected_cubic
Takes 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, edge i joining es[i].1 and es[i].2 (parallel edges allowed). It holds iff the conjunction of: (1) for every i : Fin es.length, es[i].1 < n ∧ es[i].2 < n ∧ es[i].1 ≠ es[i].2 (no loops); (2) for every v : ℕ with v < n, the Finset of i : Fin es.length with es[i].1 = v ∨ es[i].2 = v has card 3 (the multigraph is cubic); (3) the simple graph SimpleGraph.fromRel on Fin n relating u and v when some i : Fin es.length has es[i].1 = u.val ∧ es[i].2 = v.val is Connected.
Statement
def edge_list_connected_cubic (n : ℕ) (es : List (ℕ × ℕ)) : Prop
- Defined in
- arXiv:2610.35794 (Computational complexity of the H-coloring problem in cubic graphs), Sec. 1: the inputs of H-coloring are connected cubic graphs, finite, without loops, possibly with parallel edges; encoded here as an edge list on the vertices 0..n-1
- Verified
- 30 Oct 2026
- Axioms
- none listed
- Used by 5
- edge_list_h_coloring_bridgeFor a type W : Type* (any universe), let H be a simple graph on W in which every vertex x lies in exactly 3 edges ((H.incidenceSet…
- h_coloring_cubic_languageFor a type W (implicit, W : Type) and H : SimpleGraph W, h_coloring_cubic_language H : Language Bool is the set of Bool words w such that…
- petersen_colorable_of_three_edge_colorableIf es is an edge list with edge_list_connected_cubic n es that has a proper 3-edge-coloring c : Fin es.length → Fin 3 (any two distinct…
- petersen_coloring_languageThe P10-coloring decision problem as a language over Bool (Language Bool): the set of words w such that there exist n : ℕ and es : List (ℕ…
- edge_list_connected_cubic_k4The 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.
Read back from the Lean
The predicate edge_list_connected_cubic n es asserts that for a number of vertices $n : \mathbb{N}$ and an edge list $es : \text{List}(\mathbb{N} \times \mathbb{N})$:
1. For every index $i$ in es (i.e., $i : \text{Fin}(es.\text{length})$), both endpoints $es[i].1$ and $es[i].2$ are strictly less than $n$, and $es[i].1 \ne es[i].2$ (every edge connects two distinct vertices in $\{0, \dots, n-1\}$, forbidding self-loops).
2. For every vertex $v < n$, exactly 3 elements of $es$ are incident to $v$ (that is, the number of indices $i : \text{Fin}(es.\text{length})$ such that $es[i].1 = v$ or $es[i].2 = v$ is equal to 3).
3. The simple graph on vertices $\text{Fin } n$ whose adjacency relation is the symmetrization and loop-removal of the directed edges in $es$ (namely, $u \sim v$ iff $u \ne v$ and there is some edge in $es$ from $u$ to $v$ or from $v$ to $u$) is connected (which in Mathlib requires $\text{Fin } n$ to be nonempty, so $n > 0$, and every pair of vertices to be connected by a path).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- A loopless multigraph on vertices v < n, given as an edge list, is cubic and connected. -/ def edge_list_connected_cubic (n : ℕ) (es : List (ℕ × ℕ)) : Prop := (∀ i : Fin es.length, es[i].1 < n ∧ es[i].2 < n ∧ es[i].1 ≠ es[i].2) ∧ (∀ v : ℕ, v < n → (Finset.univ.filter (fun i : Fin es.length => es[i].1 = v ∨ es[i].2 = v)).card = 3) ∧ (SimpleGraph.fromRel (fun u v : Fin n => ∃ i : Fin es.length, es[i].1 = u.val ∧ es[i].2 = v.val)).Connected