Cyclic Graph — Definition, Formula & Examples

A cyclic graph is a graph that contains at least one cycle — a path that starts and ends at the same vertex without repeating any edge or intermediate vertex.

A graph $G = (V, E)$ is cyclic if there exists a sequence of distinct vertices $v_1, v_2, \ldots, v_k$ (with $k \geq 3$ ) such that $(v_i, v_{i+1}) \in E$ for all $1 \leq i \leq k-1$ and $(v_k, v_1) \in E$ . A graph with no such sequence is called acyclic.

How It Works

To determine whether a graph is cyclic, look for any closed walk that visits each vertex in the walk at most once (except for the starting vertex, which also serves as the ending vertex). In an undirected graph, a cycle must have at least 3 vertices, since traversing a single edge back and forth does not count. In a directed graph, even a loop from a vertex to itself or a pair of vertices with edges in both directions constitutes a cycle. Common algorithmic approaches include depth-first search (DFS): if DFS encounters an already-visited vertex that is not the immediate parent of the current vertex (in the undirected case), a cycle exists.

Worked Example

Problem: Determine whether the undirected graph with vertices

\{A, B, C, D\}

and edges

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

is cyclic.

Step 1: List a candidate path. Start at vertex

A

and follow edges:

A \to B \to C \to D \to A

Step 2: Check the cycle conditions. The path visits 4 distinct vertices (

k = 4 \geq 3

), each consecutive pair is connected by an edge, and the path returns to the starting vertex

A

without repeating any intermediate vertex.

Answer: The graph is cyclic because it contains the 4-cycle

A \to B \to C \to D \to A

Why It Matters

Detecting cycles is central to many algorithms in computer science. Deadlock detection in operating systems reduces to finding cycles in a resource-allocation graph. In discrete math courses, distinguishing cyclic from acyclic graphs is essential for understanding trees, topological sorting, and network flow.

Common Mistakes

Mistake: Calling an undirected graph cyclic because you can traverse an edge and immediately return (e.g.,

A \to B \to A

Correction: A cycle in an undirected graph requires at least 3 distinct vertices. Traversing a single edge back and forth is not a cycle.