Unique Paths Characterize Trees

Existence and Uniqueness of Paths

Connectedness answers whether two vertices can be joined; acyclicity rules out certain ways of joining them more than once. Together, these ideas give a precise characterization of trees: between any two distinct vertices there is exactly one path. The two parts of the statement play different roles. Connectedness supplies existence, while the absence of cycles supplies uniqueness.

Throughout, graphs are finite and simple: they have no loops or multiple edges. A path from \(u\) to \(v\) is a sequence \(v_0,v_1,\ldots,v_k\) with \(v_0=u\), \(v_k=v\), consecutive vertices adjacent, and all vertices distinct. Its length is \(k\), the number of edges in the sequence. Two paths are distinct if their vertex sequences differ. A cycle is a sequence \(v_0,v_1,\ldots,v_{\ell-1},v_0\) with consecutive vertices adjacent, \(\ell\ge 3\), and \(v_0,\ldots,v_{\ell-1}\) distinct.

The statement to prove is about all paths, not only shortest paths. A shortest path is one having minimum length among paths with the same endpoints. The characterization says there is exactly one path of any length between the chosen endpoints.

Two Distinct Paths Produce a Cycle

Proof. Let the two paths be \(P=(p_0,\ldots,p_k)\) and \(Q=(q_0,\ldots,q_\ell)\), both from \(u\) to \(v\). They start at \(p_0=q_0=u\). Let \(i\) be the last index in their common initial segment: \(p_j=q_j\) for every \(0\le j\le i\), while their next vertices differ. Such an \(i\) exists because the paths are distinct, and neither path can be a proper initial segment of the other: both end at \(v\), and a path cannot repeat \(v\).

Starting after \(p_i\), choose the first vertex \(p_j\) of \(P\) that also occurs after \(q_i\) on \(Q\). There is such a vertex because \(v\) is on both paths. Write \(p_j=q_h\). The subpath of \(P\) from \(p_i\) to \(p_j\) and the subpath of \(Q\) from \(q_i\) to \(q_h\) have the same endpoints. Their first edges differ. Their internal vertices are disjoint: if an internal vertex of the \(P\)-subpath also occurred on the \(Q\)-subpath, it would be a vertex of \(P\) occurring on \(Q\) before \(p_j\), contrary to the choice of \(j\). Thus the two subpaths form a closed sequence with no repeated vertices except its endpoints. It has at least three edges, since if both subpaths had length one they would have the same first edge. Their union is a cycle, as required. \(\square\)

The lemma is useful in both directions of the characterization. If a graph is acyclic, the lemma prevents two paths from having the same endpoints. Conversely, a cycle supplies two different paths between suitable vertices on it.

The Unique-Path Characterization

Proof. Suppose first that \(G\) is a tree. By the definition of connectedness, every pair of distinct vertices is joined by at least one path. If some pair were joined by two distinct paths, the lemma would give a cycle in \(G\). This contradicts the definition of a tree as acyclic. Therefore every pair of distinct vertices is joined by exactly one path. If \(G\) has only one vertex, there are no pairs of distinct vertices; the condition holds vacuously, and the tree has no cycle.

Conversely, suppose every pair of distinct vertices in \(G\) is joined by exactly one path. This condition gives connectedness directly: each such pair has a path. A graph with one vertex is also connected, since there is no pair of distinct vertices for which a path is required. It remains to show that \(G\) is acyclic.

If \(G\) contained a cycle \(v_0,v_1,\ldots,v_{\ell-1},v_0\), consider the distinct vertices \(v_0\) and \(v_1\). One path between them is the single edge \(v_0v_1\). Another is the path \(v_0,v_{\ell-1},v_{\ell-2},\ldots,v_1\), which follows the rest of the cycle. These paths are distinct: the first has length \(1\), and the second has length \(\ell-1\ge2\). This contradicts the assumed uniqueness. So \(G\) has no cycle. It is connected and acyclic, hence a tree. \(\square\)

The proof separates the logic cleanly: existence of paths is exactly the connectivity requirement, and uniqueness excludes cycles. The lemma makes the uniqueness direction precise without assuming that two paths must differ in a particular convenient way.

Worked Examples

What the Characterization Does—and Does Not—Say

For a tree, the unique path property gives a dependable way to describe routes: once the endpoints are specified, there is no alternative path to consider. For example, in a tree used to represent a network, the path between two locations is determined by the graph itself. The theorem is also a practical test when the structure of a graph is known: establish connectivity and rule out cycles, or establish existence and uniqueness of paths directly.

A frequent error is to confuse “unique path” with “unique shortest path.” The triangle already illustrates the difference. In the graph with \(V=\{1,2,3\}\) and \(E=\{12,23,31\}\), the direct path \(1,3\) is the unique shortest path from \(1\) to \(3\): its length is \(1\), while the other displayed path \(1,2,3\) has length \(2\). But there are two paths, so the triangle is not a tree. A shortest-path calculation alone cannot establish the unique-path condition.

Another error is to prove only one direction. Finding one path for each pair proves existence, not uniqueness. Conversely, showing that no pair has two paths does not establish that all pairs have a path: the disconnected example has pairs with no path at all. Both requirements matter, and the theorem links them to connectedness and acyclicity.