Adding One Edge to a Tree Creates One Cycle

Why One Added Edge Makes a Cycle

A tree has enough edges to connect all its vertices, but no cycles. Adding an edge between two vertices that are not already adjacent changes both features at once: the graph remains connected, and it now contains a cycle. The reason is precise. Before the addition, there is exactly one path between the chosen endpoints. The new edge closes that path, and no other cycle can appear because any cycle must use the new edge and would therefore require another path between the same endpoints.

Throughout, graphs are finite and simple: they have no loops or multiple edges. A path is a sequence of distinct vertices in which each consecutive pair is joined by an edge. Its length is the number of edges in the sequence. A cycle is a closed sequence of edges of length at least \(3\) whose vertices, apart from the repeated starting and ending vertex, are distinct. A tree is a connected acyclic graph.

Let \(u\) and \(v\) be distinct, nonadjacent vertices of a tree \(T\). Nonadjacency means \(uv\notin E(T)\), so adding \(uv\) gives a new simple graph, denoted \(T+uv\), with vertex set \(V(T)\) and edge set \(E(T)\cup\{uv\}\). The nonadjacency condition also ensures that the added edge is genuinely new. The unique \(u\)-\(v\) path in \(T\) has length at least \(2\): a path of length \(1\) would mean that \(u\) and \(v\) were already adjacent.

How Cycles Correspond to Paths

The key observation works in both directions. Starting with the unique path in the tree, adding the new edge closes it into a cycle. Conversely, any cycle in the enlarged graph must use the new edge, since the original tree had no cycles. Removing that edge from the cycle leaves a path in the original tree between its endpoints.

Proof. First take a cycle in \(T+uv\). It cannot use only edges of \(T\), because \(T\) is acyclic. Therefore it contains \(uv\). Removing \(uv\) from the cycle leaves a sequence of edges joining \(u\) to \(v\). The remaining vertices are distinct because the original sequence was a cycle, so these edges form a \(u\)-\(v\) path. All its edges belong to \(T\), since \(uv\) was the only added edge. In the other direction, take any \(u\)-\(v\) path in \(T\). Its vertices are distinct, and its length is at least \(2\) because \(u\) and \(v\) are nonadjacent. Adding the edge \(uv\) joins the two ends of the path. The result is closed, has length at least \(3\), and has no repeated vertices except for its starting and ending vertex; it is therefore a cycle. \(\square\)

Proof. Let \(P\) be the unique \(u\)-\(v\) path in \(T\). By the lemma, adding \(uv\) to \(P\) produces a cycle, so at least one cycle exists. Now take any cycle in \(T+uv\). By the lemma, it consists of \(uv\) and a \(u\)-\(v\) path in \(T\). There is exactly one such path, namely \(P\). Hence every cycle in \(T+uv\) uses exactly the same edges, those of \(P\) and \(uv\). Thus there is one cycle, and it has the stated form. \(\square\)

The uniqueness of the path is essential to the uniqueness of the cycle. The new edge does not create a cycle by itself: it joins two vertices already connected by a path. The cycle is formed by following that existing path from one endpoint to the other and then returning along the new edge.

Proof. The cycle consists of the \(k\) edges of the path and the one added edge \(uv\). Its length is therefore \(k+1\). \(\square\)

Finding the Cycle in Explicit Trees

What the Assumptions Do—and Do Not—Say

The condition that the endpoints are nonadjacent is part of the statement, not a technical detail to ignore. In a simple graph, adding an edge means adding a pair that was not already in the edge set. If \(u\) and \(v\) were already adjacent in \(T\), the edge \(uv\) would already be present, and there would be no new edge to add. The existing one-edge path between them is also their unique path, so the claimed operation would not produce a new cycle.

The tree assumption matters as well. Connectedness guarantees a path between the endpoints, while acyclicity ensures there cannot be two different paths between them. In a connected graph that already has cycles, adding an edge can create a cycle, but this argument alone does not say that there will be only one: other cycles may have existed before the addition, and several paths between the endpoints may be available. Here the original graph is a tree, so it has no old cycles and exactly one path to close.

There are no isolated or disconnected cases hidden in the theorem. A tree, by definition, is connected, so every pair of distinct vertices has a path between them. A tree with one vertex has no pair of distinct nonadjacent vertices, and a tree with two vertices has its two vertices already adjacent; neither allows the stated addition. Whenever the hypotheses do apply, the endpoints are distinct and their tree path has length at least \(2\), so the resulting cycle has length at least \(3\), as required for a cycle in a simple graph.

A Common Mistake

Mistake: In the second example, one might count only the edges on the original path and conclude that the cycle has length \(4\), because the path \(d,b,a,c,f\) has four edges.

Correction: That count omits the edge that closes the path. The path has four edges, and the newly added edge \(df\) contributes one more, so the cycle length is \(4+1=5\). In general, if the tree path has length \(k\), the cycle has \(k+1\) edges. The path and the cycle are not the same object: the path has endpoints, while the added edge joins those endpoints to make a closed sequence.

This result is useful whenever a graph is modified by adding one edge to a tree. It identifies the new cycle without searching through all possible sequences of edges: find the unique path between the endpoints, then append the new edge. The proof also supplies a check on the answer. If a proposed cycle does not contain the added edge, it cannot be a cycle in the tree-plus-edge graph, because the original tree had none.