In graph theory, a cycle graph C_n (also known as an n-cycle) is a simple undirected graph consisting of n vertices connected by n edges to form a single closed chain, where each vertex has degree exactly 2 and n \geq 3.[1][2] These graphs are the simplest connected 2-regular graphs and serve as fundamental building blocks for studying cyclic structures in more complex networks.[1]Cycle graphs exhibit several key structural properties that make them central to theoretical analysis. They are uniquely Hamiltonian, meaning they possess exactly one Hamiltonian cycle (the graph itself) up to direction, and they are also edge-transitive and vertex-transitive for n \geq 3.[1] The chromatic number of C_n is 2 if n is even (as even cycles are bipartite) and 3 if n is odd, reflecting the presence of an odd cycle that requires three colors for proper vertex coloring.[1][2] The chromatic polynomial for C_n is given by (k-1)^n + (-1)^n (k-1), where k is the number of available colors, which encapsulates their coloring behavior precisely.[2]Beyond basic properties, cycle graphs play a pivotal role in broader graph theory concepts, including extremal graph theory, where they help determine the maximum number of edges in graphs avoiding specific subgraphs like short cycles.[3] They also appear in the study of Hamiltonian and Eulerian paths, as every cycle graph is both Hamiltonian and Eulerian due to its regularity and connectivity.[2] In applications, cycle graphs model periodic or circular phenomena, such as ring networks in computer science or molecular rings in chemistry, and their cycle spaces (vector spaces over GF(2) generated by edge sets of cycles) aid in analyzing network flows and redundancies.[2] Special cases include the triangle graph C_3 (complete graph K_3) and the square graph C_4, which illustrate foundational examples in connectivity and bipartitioning.[1]
Definition and Notation
Formal Definition
In graph theory, a cycle is defined as a closed path in which no vertices are repeated except for the starting and ending vertex, which are the same.[4]The cycle graph C_n (for integer n \geq 3) is the simple undirected graph consisting precisely of a single cycle of length n, with vertex set V = \{ v_1, v_2, \dots, v_n \} and edge set E = \{ \{v_i, v_{i+1}\} \mid 1 \leq i \leq n-1 \} \cup \{ \{v_n, v_1\} \}.[1]This graph is connected and 2-regular, meaning every vertex has degree exactly 2, and it contains exactly n edges.[1]
Notation and Examples
The cycle graph on n vertices, where n \geq 3, is standardly denoted by C_n. It consists of vertices labeled v_1, v_2, \dots, v_n connected by edges \{v_i, v_{i+1}\} for i = 1, 2, \dots, n-1, along with the closing edge \{v_n, v_1\} to form a single closed loop.[1] This notation emphasizes the graph's circular structure, with each vertex having exactly two neighbors, reflecting its 2-regular nature.[1]Small examples illustrate this construction clearly. The graph C_3 is a triangle, isomorphic to the complete graph K_3, where all three vertices connect pairwise.[1] The graph C_4 resembles a square with four vertices and edges forming its perimeter, while C_5 takes the shape of a pentagon.[1] These polygonal forms underscore the cyclic symmetry inherent in cycle graphs, as rotating the labeling of vertices preserves the edge connections.[1]For C_3, the adjacency matrix, which encodes the presence of edges between vertices, is the symmetric 3×3 matrix\begin{pmatrix}
0 & 1 & 1 \\
1 & 0 & 1 \\
1 & 1 & 0
\end{pmatrix},where the off-diagonal 1's indicate edges between vertices 1-2, 2-3, and 3-1, and 0's denote no self-loops.[5] The graph C_3 is the smallest cycle graph and is 2-connected, meaning it remains connected after removing any single vertex.[6]
Terminology
Key Terms
In graph theory, a cycle is a closed walk with no repeated vertices except for the initial and terminal vertices, which coincide.[7] The girth of a graph is defined as the length of its shortest cycle; for the cycle graph C_n, this equals n.[8]Cycle graphs form a special case of circulant graphs, in which vertices correspond to elements of the cyclic group \mathbb{Z}_n and edges connect each vertex solely to its immediate neighbors (jumps of \pm 1).[9]All cycle graphs are 2-regular, with every vertex incident to exactly two edges.[10]
Distinctions from Similar Graphs
A cycle graph C_n is distinguished from the path graph P_n by the addition of an edge between its two endpoints, transforming the acyclic structure of P_n—which is a tree with exactly two vertices of degree 1—into a closed loop that introduces cyclicity while maintaining regularity of degree 2 for all vertices.[2] This closure ensures that C_n contains a Hamiltonian cycle encompassing all vertices, unlike P_n, where no such cycle exists due to its tree-like openness.[2]In comparison to the complete graph K_n, the cycle graph C_n possesses the minimal number of edges (precisely n) required for connectivity and 2-regularity, forming a sparse structure where each vertex connects only to two neighbors, whereas K_n includes \frac{n(n-1)}{2} edges, linking every pair of distinct vertices and achieving maximum density.[2] This sparsity in C_n results in a girth of n (the length of its shortest cycle), contrasting with the girth of 3 in K_n for n \geq 3.[2]The wheel graph W_n extends the cycle graph by incorporating a central hub vertex adjacent to every vertex on the n-cycle rim, increasing the total vertices to n+1 and elevating the degrees of rim vertices to 3 while the hub has degree n, whereas C_n lacks this hub and remains purely 2-regular without additional spokes.[11] Cycle graphs are 2-vertex-connected (biconnected), with no articulation points, meaning the graph remains connected after removing any single vertex, in contrast to 1-connected trees like paths, which have vertices of degree 1 and articulation points.[12]For n > 3, cycle graphs are non-chordal, as their defining induced cycle lacks any chord (an edge between non-consecutive vertices), violating the chordal graph property that every cycle of length at least 4 must contain such a chord; in contrast, chordal graphs are triangulated and free of induced cycles longer than 3.[13]
Structural Properties
Basic Structural Features
A cycle graph C_n, consisting of n vertices connected in a single closed chain, is 2-regular, meaning every vertex has exactly degree 2.[14] This regularity follows from each vertex being adjacent to precisely two others in the cycle.[2] Consequently, C_n has exactly n edges, matching the number of vertices.[15] As a connected graph with all even degrees, C_n is Eulerian, possessing an Eulerian circuit that traverses each edge exactly once.[2]The diameter of C_n, defined as the longest shortest path between any two vertices, is \lfloor n/2 \rfloor.[14] This value arises because the farthest vertices in the cycle are separated by roughly half the cycle's length.[2] Additionally, C_n is Hamiltonian by definition, as the cycle itself forms a Hamiltonian cycle that visits every vertex exactly once before returning to the start.[15]For even n, C_n is bipartite, with vertices partitionable into two independent sets of size n/2 each—alternating vertices along the cycle.[14] This bipartition is possible because even-length cycles contain no odd subcycles.[2] Moreover, C_n is triangle-free for n > 3, as the smallest cycle length is n, precluding any 3-cycles.[15]The adjacency matrix A of C_n is an n \times n circulant matrix whose first row is [0, 1, 0, \dots, 0, 1], with subsequent rows obtained by cyclic shifts; this encodes the connections to immediate neighbors.[14] For example, in C_5, it takes the formA = \begin{pmatrix}
0 & 1 & 0 & 0 & 1 \\
1 & 0 & 1 & 0 & 0 \\
0 & 1 & 0 & 1 & 0 \\
0 & 0 & 1 & 0 & 1 \\
1 & 0 & 0 & 1 & 0
\end{pmatrix}.[2]
Connectivity and Cycles
The cycle graph C_n for n \geq 3 exhibits vertex connectivity \kappa(C_n) = 2, indicating that it remains connected after the removal of any single vertex but can be disconnected by the removal of two vertices. This property arises because, for any pair of distinct vertices in C_n, there are exactly two internally vertex-disjoint paths connecting them—the two complementary arcs along the cycle—ensuring no single vertex removal severs all paths between non-adjacent vertices. By Menger's theorem, which equates the minimum number of vertices separating two non-adjacent vertices to the maximum number of internally vertex-disjoint paths between them, \kappa(C_n) = 2; specifically, removing two non-adjacent vertices splits the graph into two disjoint path components, while removing two adjacent vertices leaves a single path.[16][17]The edge connectivity of C_n is likewise \lambda(C_n) = 2, matching its minimum degree of 2 and confirming the absence of bridges (edges whose removal disconnects the graph). A minimum edge cut consists of two adjacent edges incident to the same vertex, or two non-adjacent edges that separate the cycle into two components; this renders C_n 2-edge-connected, meaning it withstands the failure of any singleedge while maintaining connectivity.[17]In terms of cycle substructures, the girth of C_n—the length of its shortest cycle—is precisely n, as the graph contains only one cycle and no chords or smaller circuits. No proper subgraph of C_n contains a cycle, so all cycles in C_n are Hamiltonian and of length n. Every connected proper subgraph of C_n is a path, reflecting its 2-regular structure; for instance, the induced subgraph on any k consecutive vertices ($1 \leq k < n) is the path graph P_k. Removing a single vertex from C_n produces the connected path P_{n-1}, while removing two non-adjacent vertices yields two disjoint paths whose lengths sum to n-2.[17]
Algebraic and Spectral Properties
Automorphism Group
The automorphism group of the cycle graph C_n for n \geq 3, denoted \mathrm{Aut}(C_n), is isomorphic to the dihedral group D_n of order $2n. This group consists of n rotations generated by a cyclic shift of the vertices and n reflections that reverse the orientation of the cycle. The order of the automorphism group is given by|\mathrm{Aut}(C_n)| = 2n.[18][19]The dihedral group D_n is generated by a rotation \rho of order n, defined by \rho(v_i) = v_{i+1 \mod n} for vertices labeled v_0, \dots, v_{n-1}, and a reflection \sigma of order 2, such as \sigma(v_i) = v_{n-i \mod n}, which fixes a vertex and the midpoint of the opposite edge (or two opposite vertices for even n). These generators satisfy the relation \sigma \rho \sigma = \rho^{-1}, capturing the symmetries of a regular n-gon.[19]The action of \mathrm{Aut}(C_n) is vertex-transitive, as rotations map any vertex to any other, and arc-transitive, as the full dihedral action permutes both directed and undirected edges transitively while preserving adjacency. This high degree of symmetry reflects the regularity of C_n, where every vertex has degree 2.[20]Cycle graphs C_n are uniquely determined up to isomorphism by their degree sequence—all vertices of degree 2—for each n \geq 3, as any connected 2-regular graph is a cycle. However, for n=4, C_4 is isomorphic to the complete bipartite graph K_{2,2}, both sharing the same degree sequence and automorphism group D_4.[21][22]
Eigenvalues and Spectrum
The adjacency matrix A of the cycle graph C_n is circulant, with 1s in the positions corresponding to edges between consecutive vertices (positions 1 and n-1 in the generating vector). The eigenvalues of such circulant matrices are derived using the discrete Fourier transform, where the k-th eigenvalue is obtained by evaluating the generating polynomial at the n-th roots of unity: \lambda_k = \omega^k + \omega^{-k}, with \omega = e^{2\pi i / n}, simplifying to \lambda_k = 2 \cos(2\pi k / n) for k = 0, 1, \dots, n-1.[23]The spectrum of A consists of these n real eigenvalues, which are symmetric around 0 due to the pairing \lambda_k = \lambda_{n-k}. The largest eigenvalue is \lambda_0 = 2, which is simple and corresponds to the all-ones eigenvector, reflecting the graph's regularity of degree 2.[23] Most eigenvalues have multiplicity 2 from these pairs, except \lambda_0 = 2 (multiplicity 1); if n is even, \lambda_{n/2} = -2 also has multiplicity 1.[23]The Laplacian matrix L = 2I - A of C_n inherits the circulant structure, yielding eigenvalues \mu_k = 2 - 2 \cos(2\pi k / n) for k = 0, 1, \dots, n-1.[24] The smallest eigenvalue is \mu_0 = 0, simple with all-ones eigenvector, while the others are positive, confirming connectivity. The algebraic connectivity, defined as the second-smallest Laplacian eigenvalue \mu_1 = 2 - 2 \cos(2\pi / n), quantifies the graph's expansion and robustness to disconnection; it approximates (2\pi / n)^2 for large n and increases monotonically with n.[25][26]
Directed Cycle Graphs
Definition
A directed cycle graph \vec{C_n} (also known as an oriented cycle graph) is a directed graph consisting of n vertices labeled v_1, v_2, \dots, v_n and n directed edges that form a single directed cycle: v_1 \to v_2 \to \dots \to v_n \to v_1.[27][28] This structure arises as the directed analogue of the undirected cycle graph C_n, where edges lack inherent direction.[1]In \vec{C_n}, every vertex has in-degree 1 and out-degree 1, as each vertex receives exactly one incoming arc and sends exactly one outgoing arc along the cycle.[28] The graph is strongly connected, meaning there exists a directed path from every vertex to every other vertex by traversing the cycle.[28] Unlike undirected cycle graphs, where edges are bidirectional, the arcs in a directed cycle graph impose a unidirectional traversal, preventing reverse paths without additional edges.[27]The smallest directed cycle graph is \vec{C_3}, forming a directed triangle with vertices v_1 \to v_2 \to v_3 \to v_1.[28]
Properties
A directed cycle graph \vec{C}_n on n vertices, where edges are oriented consistently in one direction, is strongly connected, meaning there exists a directed path from every vertex to every other vertex. Unlike the undirected cycle graph C_n, which is merely connected, the directed version ensures one-way reachability along the cycle. The diameter of \vec{C}_n is n-1, representing the maximum shortest directed path length between any pair of vertices, such as traversing almost the full cycle from one vertex to its predecessor.[29][17]Every vertex in \vec{C}_n has uniform in-degree and out-degree of 1, distinguishing it from potentially irregular orientations of cycles. This balance, combined with strong connectivity, implies that \vec{C}_n is Eulerian in the directed sense: it possesses a directed Eulerian circuit that traverses each arc exactly once, namely the cycle itself.[17]For arc coloring—assigning colors to arcs such that no two arcs sharing a common tail or head receive the same color—the chromatic number of \vec{C}_n is 1, as each vertex has at most one outgoing and one incoming arc. In contrast, the chromatic number of the underlying undirected graph is 2 if n is even and 3 if n is odd, matching that of C_n.[30][17]The automorphism group of \vec{C}_n is the cyclic group of order n, generated by rotations along the cycle; unlike the dihedral group of the undirected C_n, reflections are excluded due to the fixed edge orientations.[18]The adjacency matrix of \vec{C}_n is circulant, featuring 1's on the superdiagonal and in the bottom-left position (n,1), with 0's elsewhere:A = \begin{pmatrix}
0 & 1 & 0 & \cdots & 0 & 0 \\
0 & 0 & 1 & \cdots & 0 & 0 \\
\vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\
0 & 0 & 0 & \cdots & 0 & 1 \\
1 & 0 & 0 & \cdots & 0 & 0
\end{pmatrix}[17]\vec{C_n} contains a single directed cycle following the arc orientations, with no directed cycles possible in the opposite direction.[17]