Why a Tree Gives an Unambiguous Route
A trajectory scaffold is useful only if it specifies which route connects two cells. In a graph with cycles, there may be several simple routes between the same pair, even when their edge lengths are equal. A tree removes that topological ambiguity: between any two of its vertices there is exactly one simple path. This fact is elementary, but it is the reason a path-based description on a chosen minimum spanning tree (MST) has a definite route to refer to.
The guarantee is specific. It says that once a tree has been chosen, its vertices have unique simple paths. It does not say that the MST is the only possible MST, that the tree path is the shortest route in the original graph, or that the inferred scaffold is a biologically correct trajectory.
In this tutorial, an edge can represent a connection between two cells or cell-level representatives. If each edge \(e\) has a nonnegative length \(\ell(e)\), the length of a path \(P\) is the sum of the lengths of its edges:
The sum is well-defined once the path is specified. If all edge lengths are positive, adding edges along a path strictly increases its accumulated length. If some lengths are zero, the path remains unique as a sequence of vertices, although two different positions along it can have the same accumulated length.
The Unique-Path Theorem
The result has two separate parts. Connectedness gives at least one path. Acyclicity ensures there cannot be two different simple paths. It is important to establish both: a disconnected acyclic graph may have no path between vertices in different components, while a connected graph with a cycle can have more than one simple path.
Let \(u\) and \(v\) be vertices of a tree. The tree is connected, so a path from \(u\) to \(v\) exists. If that path repeats a vertex, remove the segment between two consecutive appearances of that repeated vertex. Repeating this removal produces a simple path.
Suppose there are two distinct simple paths from \(u\) to \(v\). Follow them from \(u\) until they first diverge. Since both end at \(v\), they eventually meet again. Choose the first vertex after the divergence on one path that also lies on the other path.
The two segments between the divergence vertex and that first meeting vertex have no shared internal vertex. Taking one segment forward and the other backward forms a cycle. This contradicts the tree's acyclicity.
There cannot be two distinct simple paths. Together with existence, this proves that exactly one simple path connects \(u\) and \(v\).
The cycle argument is the key justification. If two different simple routes were available in an acyclic connected graph, their divergence and reunion would itself create a cycle. Thus the two defining properties of a tree do different jobs: connectedness supplies a route, and acyclicity makes that route unique.
Worked Paths on a Tree
Worked Example: Finding the Unique Route and Its Length
Consider a hypothetical cell scaffold with vertices \(A,B,C,D,E\) and edges \(A-B\), \(B-C\), \(B-D\), and \(D-E\). Let their lengths, respectively, be \(1.2\), \(0.8\), \(1.5\), and \(2.0\) distance units. Find the simple path from \(A\) to \(E\) and its length.
The graph is connected: every vertex can be reached from \(B\), and therefore every pair can be connected. It is acyclic: the four edges form branches from \(B\) and \(D\), with no route returning to an earlier vertex. It is therefore a tree. By the theorem, there is exactly one simple path from \(A\) to \(E\):
The edge \(B-C\) is not on this route; reaching \(C\) and returning would repeat \(B\), so that would not be a simple path from \(A\) to \(E\). The route length is
The route is unique because of the tree structure, not because its length happens to be smaller than the length of an alternative. There is no other simple route in this graph to compare with it.
What the MST Guarantees
For a finite, connected, undirected input graph with edge costs, a minimum spanning tree is a spanning tree whose total edge cost is as small as possible among spanning trees of that graph. “Spanning” means that it includes every input vertex; it selects enough edges to connect them without retaining a cycle. The earlier material on constructing minimum spanning trees establishes how such a scaffold is obtained. The unique-path theorem supplies a further structural consequence: in any selected MST, each pair of vertices is connected by one simple tree path.
For a rooted scaffold, this means there is one combinatorial route from the root to each vertex. If the scaffold also has edge lengths, that route has a definite summed length. Those facts make the tree a well-defined object on which path-based ordering can be based. They do not, by themselves, choose a root, determine how a cell should be placed along an edge, or establish that the resulting ordering is biologically meaningful.
Worked Example: A Cycle Has Multiple Routes Until a Tree Is Selected
Suppose a hypothetical graph has four vertices \(P,Q,R,S\), with edges \(P-Q\), \(Q-S\), \(P-R\), and \(R-S\). Each edge has length \(1\). The graph contains a cycle, and there are two simple paths from \(P\) to \(S\):
Their lengths are both
There is no unique simple route in the full graph. If a spanning tree is selected by retaining \(P-Q\), \(Q-S\), and \(P-R\), then \(R-S\) is omitted. In that tree, the unique simple path from \(P\) to \(S\) is \(P-Q-S\). The unambiguous route is a property of the selected tree, not of the original cyclic graph.
Path uniqueness also does not imply that the MST itself is unique. Edge-cost ties can allow more than one spanning tree to achieve the same minimum total cost. Each candidate tree still has unique paths internally, but different candidate trees can give different paths.
Worked Example: Tied MSTs Can Give Different Paths
Consider a hypothetical triangle with vertices \(A,B,C\), and all three edge costs equal to \(1\). A spanning tree needs two edges, so each of the three possible two-edge selections has total cost
Each selection is an MST. If the selected edges are \(A-B\) and \(B-C\), the tree path from \(A\) to \(C\) is \(A-B-C\), with length \(1+1=2\). If the selected edges are \(A-C\) and \(A-B\), the tree path from \(A\) to \(C\) is the single edge \(A-C\), with length \(1\). Within either selected tree the path is unique, but the path differs across these tied MSTs.
Thus, saying “the MST gives a unique path” needs care: each particular MST gives a unique path between its vertices. When the minimum-cost tree is not unique, a reproducible analysis should also make clear which tree was selected. Distinct edge costs guarantee a unique MST, but are sufficient rather than necessary for uniqueness; some tied-cost graphs still have only one MST.
Unique Does Not Mean Shortest in the Original Graph
An MST minimizes the sum of its selected edge costs over the whole spanning tree. It does not generally minimize the path length between every pair of vertices in the original graph. This distinction matters when interpreting the length of a route on an MST: it is the length along the chosen scaffold, not automatically the shortest graph distance available before the tree was selected.
Worked Example: The Tree Route Can Be Longer Than a Direct Edge
Take three hypothetical vertices \(A,B,C\), with original graph edge lengths \(A-B=2\), \(B-C=2\), and \(A-C=3\). A minimum spanning tree retains \(A-B\) and \(B-C\), with total cost
The alternative tree retaining \(A-C\) and either length-\(2\) edge has total cost \(3+2=5\), so cost \(4\) is smaller. In the selected MST, the unique path from \(A\) to \(C\) is \(A-B-C\), with length
But in the original graph, the direct edge \(A-C\) has length \(3\), which is less than \(4\). There is no contradiction: the MST optimizes total tree cost, not every pairwise route length. A path-based quantity computed on the tree must therefore be described as a scaffold-path quantity.
Assumptions, Diagnostics, and Alternatives
The theorem applies to a simple, undirected tree. For an MST scaffold, the input graph must be finite and connected for a spanning tree to exist. The result is topological: it does not depend on the numerical edge costs once the tree has been selected. Edge lengths are needed to calculate path lengths, but they do not create path uniqueness.
- Check connectivity. If the input graph has disconnected components, no spanning tree can connect all vertices. A spanning forest has one tree per component, so vertices in different components have no connecting path.
- Check for cycles in the selected scaffold. If two distinct simple routes remain between a pair of vertices, the structure is not a tree. A path-based calculation must specify which route it uses or first select a tree.
- Check for tied MST choices. Tied costs do not always produce multiple MSTs, but they can. If different valid MSTs lead to different routes, that is structural sensitivity, not a failure of the unique-path theorem.
- Check the meaning of edge lengths. A unique route can still be a poor representation of cell relationships if the graph or its lengths are poorly matched to the data. Uniqueness is not evidence of biological validity.
A graph shortest-path calculation on a cyclic graph is an alternative when the intended object is a minimum-length route in that graph. If several routes tie for minimum length, the shortest route need not be unique. An MST instead selects a globally low-cost tree and then provides unique routes within it, but—as the example showed—those routes need not be shortest in the original graph. Principal curves, introduced in the earlier material on principal curves and their limitations at branches, represent a different approach: they describe a continuous curve and do not provide the same tree-based route structure for branching patterns. None of these choices removes the need to check whether the representation is appropriate for the data.
Common Mistakes
- Wrong reasoning: “The MST is unique, so its paths are unique.” Correction: A selected tree has unique simple paths whether or not another MST exists. The tree itself can be nonunique when costs permit ties.
- Wrong reasoning: “The unique MST path must be the shortest route in the original graph.” Correction: The MST minimizes total tree cost, not each pairwise path length.
- Wrong reasoning: “Every graph has a unique path between any two vertices.” Correction: That statement holds for trees. Cycles can create multiple simple paths, and disconnected graphs can have no path between components.
- Wrong reasoning: “A unique path proves the inferred trajectory is correct.” Correction: The theorem is conditional on the selected graph being a tree. It does not validate the cells, geometry, edge lengths, or biological interpretation.
Check Your Understanding
Answer each question, then compare your reasoning with the solutions.
- A connected graph has two distinct simple paths between vertices \(U\) and \(V\). What does this imply about the graph?
- A tree path from \(R\) to \(T\) uses edges of lengths \(0.6\), \(1.1\), and \(0.9\) distance units. Find its length and state what makes the route unique.
- Two distinct spanning trees have the same minimum total edge cost. Does this contradict the unique-path theorem?
- In the original graph, a direct edge from \(M\) to \(N\) has length \(2.5\), while their path in the selected MST has length \(3.2\). Is this inconsistent with the definition of an MST?
Solutions.
- The graph contains a cycle: the two paths diverge and later meet, and their segments between those points form a cycle. Thus it is not a tree.
- The path length is \(0.6+1.1+0.9=2.6\) distance units. Its route is unique because the selected graph is a tree: connectedness gives a path, and acyclicity rules out a second simple path.
- No. The theorem says each individual tree has exactly one simple path between each pair of its vertices. It does not require that only one minimum spanning tree exists; the two trees can have different unique paths.
- No. The MST minimizes total edge cost across a spanning tree, not every pairwise path length. A shorter direct edge can be present in the original graph but omitted from the selected tree.