# Chapter 7. Cycles and Circuits

# Chapter 7. Cycles and Circuits

A cycle is a closed path. A circuit is a closed trail. Both describe ways of returning to a starting vertex, but they control repetition differently.

A circuit may repeat vertices, but it may not repeat edges. A cycle repeats no vertices except the first and last. Thus every cycle is a circuit, but a circuit need not be a cycle. This distinction is common in graph theory texts, although terminology varies between authors.

## 7.1 Closed Walks

Let

$$
G = (V,E)
$$

be an undirected graph. A **closed walk** is a walk whose first and last vertices are the same.

Thus a closed walk has the form

$$
v_0, v_1, \ldots, v_k
$$

where

$$
v_0 = v_k
$$

and

$$
\{v_{i-1},v_i\} \in E
$$

for every

$$
1 \leq i \leq k.
$$

A closed walk may repeat vertices and edges.

For example, if the required edges exist, then

$$
a,b,c,b,a
$$

is a closed walk. It starts and ends at \(a\). It also repeats the edge \(\{b,c\}\), so it is not a trail and therefore not a circuit.

Closed walks are the broadest form of cyclic movement in a graph.

## 7.2 Circuits

A **circuit** is a closed trail.

Equivalently, a circuit is a closed walk in which no edge is repeated. Vertices may repeat.

For example, suppose the graph has edges

$$
\{a,b\}, \{b,c\}, \{c,d\}, \{d,b\}, \{d,a\}.
$$

Then

$$
a,b,c,d,b,a
$$

may be a circuit if all listed edges are distinct. The vertex \(b\) appears twice, but no edge is used twice.

The edge condition is the defining feature of a circuit. Circuits are used when the goal is to traverse edges without repetition.

## 7.3 Cycles

A **cycle** is a closed path.

More explicitly, a cycle is a vertex sequence

$$
v_0, v_1, \ldots, v_{k-1}, v_0
$$

such that

$$
k \geq 3,
$$

the vertices

$$
v_0, v_1, \ldots, v_{k-1}
$$

are distinct, and every consecutive pair is adjacent.

The integer \(k\) is the length of the cycle. It is the number of edges in the cycle.

For example,

$$
a,b,c,a
$$

is a cycle of length \(3\), also called a triangle.

The sequence

$$
a,b,c,d,a
$$

is a cycle of length \(4\) if the vertices \(a,b,c,d\) are distinct and the four required edges exist.

A cycle records a simple closed route. It returns to its starting point without revisiting any intermediate vertex.

## 7.4 Comparing Closed Walks, Circuits, and Cycles

The definitions form a hierarchy.

| Object | Closed | Repeated vertices allowed | Repeated edges allowed |
|---|---:|---:|---:|
| Closed walk | Yes | Yes | Yes |
| Circuit | Yes | Yes | No |
| Cycle | Yes | No, except start equals end | No |

Every cycle is a circuit. Every circuit is a closed walk.

The converses fail. A closed walk may repeat edges, so it may fail to be a circuit. A circuit may repeat vertices, so it may fail to be a cycle.

## 7.5 Length of a Cycle

The **length** of a cycle is its number of edges.

The cycle

$$
v_0,v_1,\ldots,v_{k-1},v_0
$$

has length

$$
k.
$$

In a simple graph, the smallest possible cycle has length \(3\). There are no cycles of length \(1\) or \(2\), because loops and parallel edges are excluded.

A cycle of length \(3\) is a triangle. A cycle of length \(4\) is often called a quadrilateral cycle or a \(4\)-cycle.

The cycle graph on \(n\) vertices is denoted by

$$
C_n.
$$

It consists of one cycle of length \(n\). Every vertex of \(C_n\) has degree \(2\).

## 7.6 Chords

Let \(C\) be a cycle in a graph \(G\). A **chord** of \(C\) is an edge of \(G\) that joins two vertices of \(C\) but is not itself an edge of the cycle.

For example, suppose

$$
C = a,b,c,d,a
$$

is a cycle. If the graph also contains the edge

$$
\{a,c\},
$$

then \(\{a,c\}\) is a chord of \(C\).

A cycle with no chord is called an **induced cycle** or **chordless cycle**. Chordless cycles are important in the study of chordal graphs, perfect graphs, and graph decomposition.

## 7.7 Girth

The **girth** of a graph is the length of its shortest cycle.

If a graph has no cycles, its girth is often taken to be

$$
\infty.
$$

For example, a triangle has girth \(3\). A square with no diagonal has girth \(4\). A tree has infinite girth under this convention, since it has no cycle.

Girth measures how locally tree-like a graph is. Large girth means that short cycles are absent.

## 7.8 Circumference

The **circumference** of a graph is the length of its longest cycle.

If a graph has no cycles, the circumference may be defined as \(0\), or left undefined, depending on convention.

Girth concerns the shortest cycle. Circumference concerns the longest cycle.

| Parameter | Meaning |
|---|---|
| Girth | Length of a shortest cycle |
| Circumference | Length of a longest cycle |

Both parameters give information about the cycle structure of the graph.

## 7.9 Acyclic Graphs

A graph is **acyclic** if it contains no cycles.

A connected acyclic graph is called a **tree**. A graph whose components are trees is called a **forest**.

Thus forests are exactly the undirected graphs with no cycles.

Acyclic graphs are structurally simpler than graphs with cycles. In an acyclic graph, there is at most one path between any two vertices in the same component. If there were two distinct paths between the same vertices, their union would contain a cycle.

## 7.10 Cycles and Connectivity

Cycles indicate redundancy of connection.

If an edge lies on a cycle, then removing that edge does not disconnect the two endpoints from each other. The rest of the cycle still gives another route between them.

For example, in the cycle

$$
a,b,c,d,a,
$$

if the edge \(\{a,b\}\) is removed, there is still a path from \(a\) to \(b\):

$$
a,d,c,b.
$$

Edges that do not lie on any cycle play a different role. Such edges may be bridges, meaning their removal increases the number of connected components. Bridges are studied later in the chapter on connectivity.

## 7.11 Eulerian Circuits

An **Eulerian circuit** is a circuit that uses every edge of a graph exactly once.

Eulerian circuits arise from edge traversal. The question is whether one can start at a vertex, traverse every edge once, and return to the start.

A connected undirected graph has an Eulerian circuit exactly when every vertex has even degree. This result is one of the classical theorems of graph theory and is closely related to Euler's study of the Seven Bridges of Konigsberg.

For example, the cycle graph \(C_n\) has an Eulerian circuit because every vertex has degree \(2\).

Eulerian circuits are about edges. They do not require visiting each vertex only once.

## 7.12 Hamiltonian Cycles

A **Hamiltonian cycle** is a cycle that visits every vertex of the graph exactly once before returning to the starting vertex.

Hamiltonian cycles are about vertices rather than edges.

For example, in a graph with vertex set

$$
V = \{v_1,v_2,\ldots,v_n\},
$$

a Hamiltonian cycle has the form

$$
v_1,v_2,\ldots,v_n,v_1,
$$

after a suitable ordering of the vertices.

A graph containing a Hamiltonian cycle is called **Hamiltonian**. Determining whether a graph has a Hamiltonian cycle is much harder than determining whether it has an Eulerian circuit. The Hamiltonian path and cycle decision problems are classical NP-complete problems.

## 7.13 Eulerian Versus Hamiltonian

Eulerian and Hamiltonian conditions should not be confused.

| Object | Must use every edge? | Must visit every vertex? | Repetition allowed? |
|---|---:|---:|---|
| Eulerian circuit | Yes | Not necessarily once | Vertices may repeat |
| Hamiltonian cycle | No | Yes, exactly once | No repeated vertices except start/end |

An Eulerian circuit controls edges. A Hamiltonian cycle controls vertices.

A graph may have one property without the other. A cycle graph \(C_n\) has both. A graph with all vertices even may have an Eulerian circuit but fail to have a Hamiltonian cycle. A graph may have a Hamiltonian cycle while some edges remain unused.

## 7.14 Directed Cycles

In a directed graph, a cycle must follow the direction of arcs.

A **directed cycle** is a sequence

$$
v_0,v_1,\ldots,v_{k-1},v_0
$$

such that the vertices \(v_0,\ldots,v_{k-1}\) are distinct and

$$
(v_i,v_{i+1}) \in A
$$

for each index, where the final arc is

$$
(v_{k-1},v_0).
$$

For example,

$$
a,b,c,a
$$

is a directed cycle if the arcs

$$
(a,b), (b,c), (c,a)
$$

exist.

A directed graph with no directed cycles is called a **directed acyclic graph**, or **DAG**. DAGs are central in scheduling, dependency analysis, compilation, dynamic programming, and topological ordering.

## 7.15 Cycle Detection

Cycle detection asks whether a graph contains a cycle.

In an undirected graph, depth-first search can detect a cycle by finding an already visited vertex that is not the parent of the current vertex in the DFS tree.

In a directed graph, depth-first search can detect a directed cycle by finding a back edge to an ancestor in the current recursion stack. Topological ordering also detects directed cycles: a finite directed graph has a topological order exactly when it is acyclic.

Cycle detection is an algorithmic version of a structural question. It asks not only whether a cycle exists, but how one can find it efficiently.

## 7.16 Independent Cycles

A graph may contain many cycles, some of which are built from others.

The **cycle rank**, also called the **cyclomatic number**, measures the number of independent cycles in an undirected graph. For a graph with \(n\) vertices, \(m\) edges, and \(c\) connected components, it is

$$
m - n + c.
$$

For a connected graph, this reduces to

$$
m - n + 1.
$$

This number is the minimum number of edges that must be removed to make the graph acyclic. It also gives the size of a cycle basis.

## 7.17 Example

Let

$$
V = \{a,b,c,d,e\}
$$

and

$$
E =
\{\{a,b\}, \{b,c\}, \{c,a\}, \{c,d\}, \{d,e\}, \{e,c\}\}.
$$

The sequence

$$
a,b,c,a
$$

is a cycle of length \(3\).

The sequence

$$
c,d,e,c
$$

is also a cycle of length \(3\).

The sequence

$$
a,b,c,d,e,c,a
$$

is a closed walk, but it is not a cycle because \(c\) appears more than once before the final return.

If no edge is repeated in that sequence, it is a circuit. It shows how circuits may contain repeated vertices while cycles may not.

## 7.18 Summary

A closed walk begins and ends at the same vertex. A circuit is a closed walk with no repeated edges. A cycle is a closed walk with no repeated vertices except the initial and terminal vertex.

Cycles describe simple closed structure. Circuits describe edge-nonrepeating closed traversal. A graph with no cycles is acyclic. A connected acyclic graph is a tree.

Eulerian circuits use every edge exactly once. Hamiltonian cycles visit every vertex exactly once. Directed cycles must follow arc directions. These ideas connect the elementary language of walks and paths with some of the central problems of graph theory.