Skip to content

Cyclicity#

Definition: Cycle

A cycle in an undirected graph is a walk

\[ (v_0, e_1, v_1, e_2, v_2, \dotsc, e_k, v_k) \]

of length \(k \ge 3\) such that:

  1. \(v_0 = v_k\);
  2. \(v_i \ne v_j\) for all distinct \(i, j \in \{0, \dotsc, k-1\}\).

Definition: Cyclicity

An undirected graph is cyclic if it contains at least one cycle and is acyclic otherwise.