Cycles and Closed Paths

When Is a Closed Route a Cycle?

A route can return to its starting vertex without tracing a cycle. It might repeat an edge, revisit a vertex along the way, or simply traverse one edge and then immediately traverse it back. The word cycle is reserved for a more specific kind of closed route: apart from its required return to the starting vertex, it does not repeat any vertex.

Throughout, graphs are finite and simple: they have no loops and no multiple edges. A walk is a sequence \(v_0,v_1,\ldots,v_k\) in which each consecutive pair is joined by an edge; its length is \(k\). A walk is closed if \(v_k=v_0\). A trail is a walk that does not repeat an edge. A path is a walk that does not repeat a vertex. A path of length zero, consisting of one vertex, is allowed.

One sometimes describes a cycle as a “closed path,” meaning a path-like sequence that returns to its start. Strictly, a path has no repeated vertices, so the cycle definition explicitly allows the first vertex to appear again at the end. The condition \(k\ge3\) follows naturally for cycles in simple graphs: a loop would be needed for length one, and a length-two closed sequence would traverse the same edge twice. Neither is a cycle here.

Checking the Conditions

To decide whether a sequence is a cycle, check the requirements separately. First, every consecutive pair must be an edge of the graph. Next, the sequence must close. Then check that the length is at least three and that the vertices before the final return are all distinct. A sequence can satisfy some of these checks and still fail to be a cycle.

How Cycles Relate to Walks and Trails

Every cycle is a closed trail, and every closed trail is a closed walk. The reverse implications do not hold: a closed walk may repeat an edge, and a closed trail may revisit a vertex even though it never repeats an edge.

Proof. Let \(v_0,v_1,\ldots,v_k=v_0\) be a cycle. It is closed by its defining equality \(v_k=v_0\), so it is a closed walk. Its vertices \(v_0,\ldots,v_{k-1}\) are distinct and \(k\ge3\). Hence each of its edges joins a different consecutive pair around the sequence: no edge can occur twice. Thus it is a trail.

To show that the reverse implications fail, consider the explicitly defined simple graph with \(V=\{a,b,c,d,e\}\) and \(E=\{ab,bc,ca,ad,de,ea\}\). The sequence \(a,b,c,a,d,e,a\) is closed: its consecutive edges are \(ab,bc,ca,ad,de,ea\), and it returns to \(a\). These six edges are all distinct, so it is a closed trail. However, \(a\) occurs at positions \(1,4,\) and \(7\), so the sequence is not a cycle.

In the same graph, the sequence \(a,b,c,b,a\) is a closed walk with consecutive edges \(ab,bc,cb,ba\). It repeats the edges \(bc\) and \(ab\), so it is not a trail. This proves both failures of the reverse implications. \(\square\)

The proposition describes a one-way inclusion: cycles are among the closed trails, which are among the closed walks. To decide which category a particular sequence belongs to, inspect its actual vertex and edge repetitions rather than relying only on the fact that it returns to its start.

The Edges and Vertices of a Cycle

Although a cycle is specified by a sequence, it also determines a subgraph: take its vertices and just the edges used in the sequence. In this subgraph, each vertex is incident with exactly two of the cycle’s edges—one arriving and one departing. This includes a triangle: its three edges are distinct, and each of its three vertices is incident with two of them.

Proof. Let \(v_0,v_1,\ldots,v_k=v_0\) be a cycle, where \(k\ge3\) and \(v_0,\ldots,v_{k-1}\) are distinct. The cycle edges are \(v_0v_1,v_1v_2,\ldots,v_{k-2}v_{k-1},v_{k-1}v_0\). Each vertex \(v_i\) is incident with the edge preceding it in this list and the edge following it, with the list understood cyclically. These are distinct edges: if \(k=3\), they are two different sides of the triangle; if \(k>3\), their other endpoints are distinct because the vertices \(v_0,\ldots,v_{k-1}\) are distinct. The subgraph contains no other edges by its definition, so each of its vertices has degree exactly \(2\). \(\square\)

This statement concerns the subgraph made from the cycle edges, not necessarily the whole graph. The original graph may contain additional edges between vertices of the cycle or from those vertices to other vertices. Those additional edges are not part of the cycle’s edge list.

Common Pitfalls

Counting a back-and-forth traversal as a cycle. In a simple graph, the sequence \(u,v,u\) has length \(2\) and traverses the edge \(uv\) twice. It is a closed walk, but not a trail or cycle. A cycle must have length at least \(3\).

Checking only whether the sequence closes. Returning to the starting vertex is necessary for a cycle, but it is not enough. The sequence \(a,b,c,a,d,e,a\) above closes and uses no edge twice, yet revisits \(a\) before the final return. It is a closed trail, not a cycle.

Confusing the cycle with the whole graph. A graph may contain a cycle and also have extra edges. When checking the degree-\(2\) property, use only the edges of the cycle subgraph. Extra edges in the ambient graph do not alter whether the specified sequence is a cycle.