1 Definition and Basic Properties

1.1 Formal definition of \(C_n\)

The cycle graph \(C_n\) is the simple graph whose vertex set consists of \(n\) vertices arranged in a closed chain, with edges joining consecutive vertices and also the first to the last. Formally, one may index vertices by \(\{0,1,\dots,n-1\}\) and define edges \(\{i,i+1\}\) for \(i\) taken modulo \(n\). The condition \(n\ge 3\) ensures the structure is nondegenerate and forms a single cycle.

1.2 Degree sequence and adjacency structure

Every vertex in \(C_n\) has degree 2. The graph is 2-regular, meaning each vertex is incident to exactly two edges: one connecting it to its predecessor along the cycle and one connecting it to its successor. This uniform degree distribution is a key reason cycles are both symmetric and mathematically tractable.

1.3 Small examples (e.g., \(C_3\), \(C_4\), \(C_5\))

For \(n=3\), \(C_3\) is a triangle: three vertices with edges between each pair, each vertex connected to the other two. For \(n=4\), \(C_4\) is a square with a “cycle” around four vertices; vertices are not connected diagonally, so the graph is not complete. For \(n=5\), \(C_5\) is a pentagon; again, adjacency follows only consecutive vertices in the circular order. These examples illustrate how properties begin to diverge with parity and size, especially in coloring and spectral behavior.

1.4 Graph isomorphism and labeling conventions

All cycle graphs with the same number of vertices are isomorphic: \(C_n\) is uniquely determined up to relabeling of vertices. In practice, authors adopt a cyclic indexing convention so that vertex labels wrap around modulo \(n\). Such conventions streamline formulas for adjacency, distances, and symmetries.

2 Representations and Notation

2.1 Adjacency matrix of a cycle

The adjacency matrix \(A(C_n)\) is an \(n\times n\) binary matrix where \(A_{ij}=1\) exactly when vertices \(i\) and \(j\) are adjacent. With cyclic labeling, \(A_{i,i+1}=A_{i+1,i}=1\) for each \(i\) modulo \(n\), and all other entries are 0. The matrix is sparse, with exactly two ones in each row and column.

2.2 Incidence matrix perspective

An incidence matrix describes how vertices meet edges. For \(C_n\), each edge corresponds to a pair of consecutive vertices, so each column of the incidence matrix has two 1 entries (over \(\mathbb{Z}\)) and every vertex participates in exactly two edges. This representation is frequently used when discussing linearly independent constraints or relating graph structure to algebraic objects.

2.3 Edge set and cyclic indexing

A common way to write the edge set is \[ E(C_n)=\bigl\{\{i,i+1\}\;:\; i\in \mathbb{Z}_n \bigr\}, \] where \(\mathbb{Z}_n\) denotes integers modulo \(n\). This notation emphasizes that the cycle “closes” by identifying \(n\) with \(0\), so the edge \(\{n-1,0\}\) is included automatically.

2.4 Geometric/circular drawing conventions

Cycle graphs are often drawn as vertices around a circle with straight or slightly curved edges connecting neighbors. While drawings are not part of the formal graph, the circular layout matches the indexing convention and makes symmetries, paths along the perimeter, and distance along the ring easier to visualize.

3 Symmetry and Automorphisms

3.1 Rotational symmetries

A rotation of the cycle maps each vertex to the one \(k\) steps ahead (modulo \(n\)). Under such a permutation, adjacency is preserved because “neighbors” remain neighbors after shifting labels around the ring. These rotations form a cyclic family of symmetries.

3.2 Reflection symmetries

A reflection reverses the cyclic order: intuitively, it flips the drawing across an axis, sending the clockwise direction to counterclockwise while keeping the set of vertices fixed. Algebraically, it corresponds to mapping index \(i\) to an affine function of \(i\) modulo \(n\) that reverses order. Reflections also preserve adjacency because consecutive vertices in one direction remain consecutive in the reversed direction.

3.3 Automorphism group of \(C_n\)

The automorphism group captures all vertex permutations that preserve edges. For \(n\ge 3\), the automorphism group of the cycle is the dihedral group: it consists of \(n\) rotations and \(n\) reflections, totaling \(2n\) automorphisms. This structure underlies many “orbit” and invariance arguments.

3.4 Orbits of vertices and edges

Because the cycle is vertex-transitive, all vertices lie in a single orbit under automorphisms. Edges also form a single orbit as long as adjacency patterns remain uniform around the ring. For certain derived structures (such as directed edges or chosen starting points), orbits can split, but in the standard undirected cycle the base symmetry is strongly uniform.

4 Connectivity and Distances

4.1 Vertex and edge connectivity

Cycle graphs are connected. Removing a single vertex breaks the cycle into a path, so \(C_n\) has vertex connectivity \(\kappa(C_n)=2\). Similarly, removing a single edge turns it into a path, so the edge connectivity is also \(\lambda(C_n)=2\). Intuitively, two independent ways exist to route between any two nearby points along the ring.

4.2 Diameter of \(C_n\)

The diameter is the maximum distance between any pair of vertices. On a cycle, the farthest two vertices are opposite or near-opposite along the perimeter. Consequently, \[ \operatorname{diam}(C_n)=\left\lfloor \frac{n}{2}\right\rfloor. \]

4.3 Distance between vertices

The distance between two vertices equals the length of the shorter of the two perimeter segments connecting them. If vertices are \(i\) and \(j\), one can compute the minimal step count around the ring from \(i-j\) and its complement to \(n-i-j\).

4.4 Paths and geodesics on a cycle

Between two vertices, there are one or two shortest paths depending on whether the vertices are uniquely determined by the shorter arc. If \(n\) is even and the vertices are opposite, there are exactly two distinct geodesics, each following one of the two equal-length arcs. Otherwise, the shortest route is unique.

5.1 Identifying cycles within a cycle graph

A cycle graph contains essentially one simple cycle that uses all vertices. However, smaller cycles do not occur as induced cycles within a plain cycle graph: \(C_n\) has no triangles for \(n\ge 4\), and more generally it has no smaller simple cycles because edges are arranged only between consecutive vertices.

5.2 Induced subgraphs of \(C_n\)

An induced subgraph is determined by choosing a subset of vertices and retaining all edges among them. For \(C_n\), induced subgraphs can form disjoint unions of paths when the chosen vertices break the ring into segments. If all vertices are chosen, the induced subgraph is \(C_n\) itself.

5.3 Paths as subgraphs of \(C_n\)

Any consecutive run of \(k\) vertices along the cycle (without wrapping) induces a path of length \(k-1\). Thus, paths occur naturally as connected induced subgraphs when the vertex subset does not include a complete wrap-around segment.

5.4 Comparisons with path graphs \(P_n\)

A path graph \(P_n\) is like a cycle graph with an edge removed; it is not 2-regular and has endpoints of degree 1. Many parameters on cycles resemble those on paths, but distances and symmetry differ: cycles have periodic structure and potentially two equal shortest routes, whereas paths have unique shortest paths and a linear “end” structure.

6 Graph Invariants

6.1 Number of vertices and edges

For \(C_n\), the number of vertices is \(n\) and the number of edges is also \(n\). This equality reflects the 2-regular property: summing degrees gives \(2n\), which corresponds to \(n\) edges.

6.2 Degree-based invariants

Because each vertex has the same degree (2), degree-based invariants such as the degree sequence and degree multiset are uniform across all vertices. The regularity of \(C_n\) simplifies many formulas, including those related to Laplacian structure and counting via local constraints.

A matching is a set of edges no two of which share a vertex. For cycle graphs, the maximum size of a matching depends on \(n\). When \(n\) is even, a perfect matching exists (all vertices can be paired by disjoint edges). When \(n\) is odd, the largest matching leaves one vertex unmatched. Counting matchings of all sizes follows recurrence patterns tied to the cyclic arrangement.

6.4 Independence number and vertex covers

An independent set is a set of vertices with no edges between them. On a cycle, independence size depends on how vertices can be spaced around the ring without adjacency. For example, one can alternate vertices around the cycle, yielding sizes closely related to \(\lfloor n/2\rfloor\), with parity determining exact optimal values. Complementary notions like vertex covers are connected by standard dualities: the size of a minimum vertex cover relates to the maximum independent set.

7 Chromatic and Coloring Results

7.1 Chromatic number of \(C_n\)

The chromatic number is the minimum number of colors needed for a proper vertex coloring. For cycle graphs:

  • \(C_n\) is 3-colorable for all \(n\).
  • In fact, the chromatic number is 2 when \(n\) is even and 3 when \(n\) is odd.

Even cycles can be colored with two alternating colors, while odd cycles require a third color due to the parity obstruction.

7.2 Proper vertex colorings and patterns

Proper colorings on a cycle follow a simple constraint: adjacent vertices must differ, so colors propagate around the ring. With two colors, consistency around the entire cycle works exactly for even \(n\). For odd \(n\), using three colors allows one to close the chain while resolving the parity conflict.

7.3 Chromatic polynomial overview

The chromatic polynomial \(\chi_{C_n}(k)\) counts proper colorings using \(k\) colors. For cycles, it has a closed form derived from recurrence relations or transfer-matrix methods, reflecting the cyclic constraint when the coloring wraps around. The polynomial specializes to the chromatic number statement for \(k=2\) (even cycles) and \(k=3\) (odd cycles).

7.4 Edge coloring connections (where applicable)

While vertex coloring is most standard for cycles, edge-coloring can also be studied. For cycle graphs, edge-coloring relates to whether the cycle is even or odd, and to whether one can assign colors to edges so that incident edges at each vertex differ. The cyclic regularity keeps the analysis comparatively straightforward.

8 Spectral Properties

8.1 Eigenvalues of the adjacency matrix

The adjacency matrix of \(C_n\) has a well-known spectrum expressible using roots of unity. The eigenvalues are \[ \lambda_j=2\cos\left(\frac{2\pi j}{n}\right),\quad j=0,1,\dots,n-1. \] This closed form arises from the circulant structure: adjacency corresponds to shifts by one step in either direction.

8.2 Laplacian eigenvalues and algebraic connectivity

The Laplacian matrix \(L=D-A\) equals \(2I-A\) for \(C_n\) because the degree matrix \(D\) is \(2I\). The Laplacian eigenvalues are \[ \mu_j = 2-2\cos\left(\frac{2\pi j}{n}\right)=4\sin^2\left(\frac{\pi j}{n}\right). \] The smallest eigenvalue is 0 (reflecting connectedness). The second-smallest eigenvalue, often called the algebraic connectivity, quantifies how robustly connected the graph is and decreases as \(n\) grows.

8.3 Eigenvectors and interpretation

Eigenvectors can be chosen as discrete Fourier modes around the cycle. Each eigenvector encodes a “wave pattern” whose phase advances uniformly along the ring. Higher-frequency modes oscillate more rapidly, while low-frequency modes relate to global structure such as diameter-scale separation.

8.4 Spectral consequences for walk structure

Spectral data govern counts of walks and the long-run behavior of random walks on the cycle. Since eigenvalues control transition dynamics, properties like mixing speed and the prevalence of returning to a starting vertex can be studied through spectral expansions.

9 Walks, Counting, and Combinatorics

9.1 Number of walks of given length

A walk is a sequence of vertices where consecutive vertices are adjacent. On \(C_n\), the number of walks of a fixed length from a starting vertex depends only on the displacement along the cycle, not on the absolute label, due to symmetry. These counts can be derived using recurrence relations or matrix powers of the adjacency matrix.

9.2 Recurrences from cyclic structure

Because each vertex has exactly two neighbors, walk counts satisfy linear recurrences. When tracking walks that respect the cycle wrap-around, one obtains equations reminiscent of those for paths, but with boundary conditions replaced by periodicity.

9.3 Closed walks and counting techniques

Closed walks start and end at the same vertex. The cycle allows many closed routes, from small back-and-forth steps to large tours around the ring. Closed-walk counts can be computed via spectral methods (summing eigenvalue powers) or through combinatorial decompositions that track how many times a walk winds around the cycle.

9.4 Applications to cyclic combinatorial identities

These counting results often feed into identities involving trigonometric sums and binomial-type expansions. Since eigenvalues have cosine expressions, many combinatorial quantities on \(C_n\) connect naturally to trigonometric forms and cyclic symmetries.

10 Algorithmic Aspects and Computations

10.1 Efficient computation of invariants on cycles

Many invariants of \(C_n\) admit closed forms, allowing direct computation without expensive general graph algorithms. Quantities such as degrees, diameter, chromatic number, and spectral radii can be obtained using formulas based on \(n\) and parity.

10.2 Traversal algorithms (BFS/DFS) behavior on \(C_n\)

Breadth-first search and depth-first search on a cycle exhibit predictable patterns. BFS layers correspond to distance along the ring, expanding outward symmetrically until the farthest vertices are reached at radius \(\lfloor n/2\rfloor\). DFS depends on neighbor ordering but still explores the cycle systematically.

10.3 Dynamic programming on cycles

Dynamic programming can exploit the local rule “each vertex has two choices” for many counting problems. For example, one can count independent sets, matchings, or colorings by processing vertices along the cycle, with special handling needed to enforce the wrap-around constraint.

10.4 Complexity notes and implementation considerations

For cycles, the asymptotic complexity of many computations is favorable because the graph is sparse and highly structured. In general graphs, the same task might be computationally hard, but on \(C_n\) symmetry and regularity often permit polynomial-time solutions or even constant-time formulas once \(n\) is known.

11 Extensions and Variants

11.1 Cycles with chords (comparison conceptually)

Adding a chord to \(C_n\) introduces an extra edge between nonconsecutive vertices, breaking the pure cycle structure. This creates additional cycles and alters distances, connectivity, and spectral properties. Conceptually, the cycle serves as a baseline for understanding how one extra edge changes global behavior.

11.2 Power of a cycle graph (high-level overview)

The \(k\)th power of a cycle graph connects vertices within distance \(k\) along the ring. As \(k\) increases, the graph becomes more densely connected, and parameters such as diameter shrink. The power construction retains some cyclic symmetry while modifying adjacency rules.

11.3 Cartesian products involving cycles (brief)

Cartesian products of graphs combine structures so that adjacency reflects movement in one factor at a time. Using a cycle as one factor produces graphs with layered circular geometry (often interpreted as grids on a cylinder-like topology). Many properties then relate to those of each factor.

11.4 Infinite cycle graph intuition (conceptual)

An “infinite cycle” can be imagined as an infinite path with periodic identification removed: effectively, a line extending without wrap-around. While not a finite simple graph, this intuition helps interpret limits of distance, spectral behavior, and walk growth as \(n\) becomes large.