Cycle¶

Definition¶

In the course's network terminology, a cycle or tour is a path that starts and ends at the same vertex. Because its path convention requires distinct edges, no edge is repeated within such a cycle.

Interpretation¶

A cycle is a route that ends where it started. In the course's convention it is a path whose first and last vertices coincide, so no edge is used twice. Cycles describe routes that must return home, and they are excluded when constructing a tree.

A network from A to F with the closed path B, D, E, C, B highlighted as a cycle.

The red cycle $B-D-E-C-B$ uses the four edges $B-D$ $D$ , $D-E$ $E$ , $E-C$ and $C-B$ $B$ , each once, and returns to $B$ .

Only repeated edges are forbidden, so a cycle may pass through a vertex twice, like a figure of eight. Removing one edge of a cycle keeps the network connected, because the rest of the cycle still joins its two ends; this is why the Kruskal method rejects an edge that closes a cycle and a spanning tree contains none.

Key Results¶

An Euler tour is a closed traversal using every edge exactly once.
A tree contains no cycles.
In the Chinese postman problem, “tour” is also used for a closed route that may repeat original edges; repeated copies are distinct in the augmented network.

Examples¶

The red cycle in the figure is $B-D-E-C-B$ $B$ . An undirected network with no cycles is a forest; when it is also connected, it is a tree.

Three edges $A-B$ $B$ , $B-C$ $C$ , and $C-A$ form a cycle.
Adding an edge between two already connected vertices of a tree creates a cycle.

Prerequisites¶

Path in a Network

Sources¶

OR Modelling · Week 4

Aliases: closed path

Last updated: 20 October 2026 03:02