is_circulant_graph
def
A simple graph G on N vertices is circulant if it is isomorphic to the Cayley graph of ZMod N with respect to some connection set s.
Statement
def is_circulant_graph {V : Type*} (N : ℕ) (G : SimpleGraph V) : Prop
- Defined in
- arXiv:2610.31807 Section 8
- Verified
- 26 Oct 2026
- Axioms
- none listed
- Used by 2
- order_eight_hankel_not_circulantAny simple graph on ZMod 8 whose adjacency is given by (x + y).val ∈ {1, 3, 5} is not a circulant graph on ZMod 8.
- exists_non_circulant_sharp_cyclic_graph_order_eightThere exists a simple graph G on ZMod 8 with at least one edge that admits a sharp cyclic labeling and is not a circulant graph on ZMod 8.
Read back from the Lean
Given a type V, a natural number N, and a simple graph G on V, is_circulant_graph N G asserts that there exists a subset s of ZMod N such that G is isomorphic (as a simple graph) to the circulant graph on ZMod N with connection set s (SimpleGraph.circulantGraph s).
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 simple graph on N vertices is circulant if it is isomorphic to a circulant graph on ZMod N. -/ def is_circulant_graph {V : Type*} (N : ℕ) (G : SimpleGraph V) : Prop := ∃ s : Set (ZMod N), Nonempty (G ≃g SimpleGraph.circulantGraph s)