Graph Cycle — Definition, Formula & Examples

A graph cycle is a path through a graph that starts and ends at the same vertex, visiting each intermediate vertex exactly once. In other words, it is a closed loop with no repeated vertices or edges.

A cycle in a graph $G = (V, E)$ is a sequence of distinct vertices $v_1, v_2, \ldots, v_k$ (where $k \geq 3$ ) such that $(v_i, v_{i+1}) \in E$ for all $1 \leq i \leq k-1$ , $(v_k, v_1) \in E$ , and all $v_i$ are distinct. A cycle of length $k$ is denoted $C_k$ .

How It Works

To identify a cycle in a graph, look for a sequence of edges that forms a closed loop without revisiting any vertex along the way. The length of the cycle equals the number of edges (equivalently, the number of distinct vertices) in the loop. A triangle is the smallest possible cycle,

C_3

. A graph with no cycles is called acyclic — trees are the most common example of connected acyclic graphs. Cycle detection is a fundamental operation in algorithms such as depth-first search.

Worked Example

Problem: Consider a graph with vertices

\{A, B, C, D\}

and edges

\{(A,B), (B,C), (C,D), (D,A), (A,C)\}

. Find all cycles of length 3 and 4.

Step 1: Check for 3-cycles (triangles). Look for sets of three vertices that are all mutually connected.

A \to B \to C \to A \quad \text{uses edges } (A,B),\,(B,C),\,(A,C) \checkmark

Step 2: Check the other triple

\{A, C, D\}

A \to C \to D \to A \quad \text{uses edges } (A,C),\,(C,D),\,(D,A) \checkmark

Step 3: Check for a 4-cycle using all four vertices without the diagonal edge

(A,C)

A \to B \to C \to D \to A \quad \text{uses edges } (A,B),\,(B,C),\,(C,D),\,(D,A) \checkmark

Answer: The graph contains two 3-cycles (

A

B

C

and

A

C

D

) and one 4-cycle (

A

B

C

D

Why It Matters

Cycle detection is central to algorithms in discrete mathematics and computer science. Determining whether a graph is acyclic decides if it can serve as a tree structure or a valid DAG for topological sorting. Cycles also appear in network analysis, circuit design, and scheduling problems where circular dependencies must be identified.

Common Mistakes

Mistake: Confusing a cycle with a general closed walk that revisits vertices.

Correction: A cycle requires all vertices in the sequence to be distinct (except that the starting vertex equals the ending vertex). A closed walk that revisits intermediate vertices is not a cycle.