Cycle Graph — Definition, Formula & Examples

A cycle graph is a graph where every vertex has exactly two edges, and the vertices form a single closed loop with no branches or dead ends.

The cycle graph $C_n$ on $n \geq 3$ vertices is a 2-regular connected graph in which the vertex set $\{v_1, v_2, \ldots, v_n\}$ has edge set $\{\{v_i, v_{i+1}\} : 1 \leq i \leq n-1\} \cup \{\{v_n, v_1\}\}$ . It has exactly $n$ edges and is the unique (up to isomorphism) connected graph on $n$ vertices where every vertex has degree 2.

Key Formula

|E(C_n)| = n, \quad \deg(v) = 2 \text{ for all } v \in V(C_n)

Where:

$C_n$ = The cycle graph on n vertices
$n$ = Number of vertices (must be at least 3)
$|E(C_n)|$ = Number of edges in the cycle graph
$\deg(v)$ = Degree of each vertex

Worked Example

Problem: Determine the number of edges, the chromatic number, and whether the cycle graph

C_5

is bipartite.

Edges: A cycle graph on

n

vertices always has exactly

n

edges.

|E(C_5)| = 5

Bipartiteness: A cycle graph

C_n

is bipartite if and only if

n

is even. Since 5 is odd,

C_5

is not bipartite.

Chromatic number: For odd cycles, you need 3 colors to properly color the vertices (no two adjacent vertices share a color). For even cycles, 2 colors suffice.

\chi(C_5) = 3

Answer:

C_5

has 5 edges, is not bipartite, and has chromatic number 3.

Why It Matters

Cycle graphs appear throughout discrete mathematics and computer science. Detecting cycles in directed graphs is essential for topological sorting and deadlock detection in operating systems. Odd versus even cycle structure also determines whether a graph is bipartite, a key classification used in matching algorithms and network flow problems.

Common Mistakes

Mistake: Confusing a cycle graph

C_n

with a cycle (subgraph) within a larger graph.

Correction: A cycle graph

C_n

is a standalone graph that consists entirely of a single cycle. A cycle in a general graph is a closed walk with no repeated vertices embedded inside a potentially much larger structure.