Structure of Finite Connected 2-Regular Simple Graphs as Cycle Graphs
ProvedOPG37271.two_regular_connected_iso_cycleGraphcombinatoricscyclesgraph-theory
Every nonempty finite connected -regular simple graph has at least vertices and is isomorphic to the standard cycle graph on .
Preamble
import Definitions.Def_opg37271_star_edge_coloring import Mathlib.Combinatorics.SimpleGraph.Connectivity.Connected import Mathlib.Combinatorics.SimpleGraph.Maps universe u namespace OPG37271
Formal statement
theorem two_regular_connected_iso_cycleGraph
{W : Type u} [Fintype W] (H : SimpleGraph W)
(hne : Nonempty W) (hconn : H.Connected)
(hreg : ∀ w : W, (H.neighborSet w).encard = 2) :
3 ≤ Fintype.card W ∧
Nonempty (H ≃g SimpleGraph.fromRel
(fun i j : Fin (Fintype.card W) => (i.val + 1) % Fintype.card W = j.val)) := by sorry
end OPG37271Source
Standard structural classification of 2-factors into disjoint cycles, used in Dvořák, Mohar, and Šámal (2013), Section 4.