Why Use a Rooted One-Tree?
A spanning tree is a simple lower-bound object for the traveling salesman problem: it connects all the cities without requiring a return route. A rooted one-tree adds a specific requirement at a chosen root: the root must have exactly two incident edges. This captures part of the structure of a tour while allowing the other vertices to have degrees that a tour would not permit. Minimizing over these relaxed objects gives a lower bound on the cost of an optimal tour.
Throughout, a TSP instance is a complete, undirected, simple graph \(G=(V,E)\) with a real weight \(w(e)\) assigned to each edge. The graph is complete so every pair of distinct vertices has an edge. Assume \(n=|V|\ge3\). A Hamiltonian tour is a cycle that visits every vertex exactly once before returning to its start; its weight is the sum of its edge weights. No triangle inequality is needed for the results below.
The two root edges must go to distinct vertices because the graph is simple. The spanning tree has \(n-2\) edges, so a rooted one-tree has \(n\) edges. It is connected: the nonroot vertices are connected by the spanning tree, and the two root edges attach \(r\) to that tree. Every vertex other than \(r\) has degree at least one, but it need not have degree two. That distinction is why a one-tree need not be a tour.
Why the Minimum One-Tree Is a Lower Bound
Proof. Let \(T\) be any Hamiltonian tour. Write its cyclic order starting at \(r\) as \(r,v_1,v_2,\ldots,v_{n-1},r\). Delete the two tour edges \(rv_1\) and \(v_{n-1}r\). The remaining edges form the path \(v_1v_2\cdots v_{n-1}\), which is a spanning tree on \(V\setminus\{r\}\): it contains every nonroot vertex, is connected, and has no cycle. Restoring the two deleted edges gives exactly \(T\), so \(T\) is itself a rooted one-tree. The minimum weight among rooted one-trees is no greater than the weight of this particular one-tree \(T\). Since \(T\) was arbitrary, the inequality holds for every tour, including an optimal one. \(\square\)
The theorem compares the minimum one-tree weight with tour weights. It does not say that every one-tree is cheaper than every tour. A different one-tree can have higher weight than a particular tour. The useful point is that the set of rooted one-trees includes every tour, while it may also include cheaper structures that are not tours.
How to Compute a Minimum Rooted One-Tree
Proof. The edges of a rooted one-tree fall into two disjoint sets: the \(n-2\) edges of its spanning tree on \(V\setminus\{r\}\), and its two edges incident with \(r\). The first set has weight at least the weight of a minimum spanning tree on the nonroot vertices. The second set has weight at least the sum of the two cheapest distinct root-edge weights. Thus every rooted one-tree has weight at least the sum of these two minima. Conversely, choose a minimum spanning tree on the nonroot vertices and the two cheapest distinct root edges. They do not overlap, since the tree has no edge incident with \(r\); together they form a rooted one-tree. Its weight equals the stated sum, so it attains the minimum. \(\square\)
This separates the computation into two independent choices. A minimum spanning tree can be found using the standard methods for that problem; the two root edges are selected by sorting the weights of the \(n-1\) edges incident with \(r\). If weights tie, any tied choices that are distinct edges give the same minimum value.
Worked Example: Computing a Minimum One-Tree
Let \(V=\{r,a,b,c,d\}\), with the complete graph whose edge weights are listed below. The root is \(r\).
| Edges not incident with \(r\) | Weight | Edges incident with \(r\) | Weight |
|---|---|---|---|
| \(bc\) | 1 | \(ra\) | 2 |
| \(ab\) | 2 | \(rc\) | 3 |
| \(ac\) | 3 | \(rb\) | 5 |
| \(bd\) | 4 | \(rd\) | 6 |
| \(cd\) | 5 | ||
| \(ad\) | 6 |
First find a minimum spanning tree on \(\{a,b,c,d\}\). In increasing order, the edges are \(bc\) of weight \(1\), \(ab\) of weight \(2\), \(ac\) of weight \(3\), \(bd\) of weight \(4\), \(cd\) of weight \(5\), and \(ad\) of weight \(6\). Select \(bc\), which joins \(b\) to \(c\), then \(ab\), which joins \(a\) to that component. The edge \(ac\) would complete a cycle on \(a,b,c\), so do not select it. Select \(bd\), which adds \(d\). The spanning tree is \(\{bc,ab,bd\}\), with weight \(1+2+4=7\). It connects all four nonroot vertices using three edges.
The two cheapest distinct root edges are \(ra\), of weight \(2\), and \(rc\), of weight \(3\). The minimum rooted one-tree therefore has edge set \(\{bc,ab,bd,ra,rc\}\) and weight \(7+2+3=12\).
Check: the tree has \(4-1=3\) edges, and adding two root edges gives \(5\) edges, equal to \(n=5\). The tree connects \(a,b,c,d\), and both \(ra\) and \(rc\) attach \(r\), so the one-tree is connected. Its weight recomputes directly as \(1+2+4+2+3=12\). The theorem proves this is minimum: each of its two separate parts is minimum in its own choice.
A One-Tree Can Fail to Be a Tour
A tour has degree two at every vertex. In a rooted one-tree, only the root is required to have degree two; the other degrees are not constrained. More precisely, a rooted one-tree has a unique cycle, and that cycle contains the root. To see this, the nonroot spanning tree has a unique path between the endpoints of the two root edges. That path together with the two root edges forms a cycle. Any cycle in the one-tree would have to use the root, since the nonroot edges form a tree; using both root edges forces it to be exactly the cycle just described. Branches of the spanning tree can attach to this cycle, giving nonroot vertices degree greater than two.
Worked Example: A Minimum One-Tree That Is Not a Tour
Let \(V=\{r,a,b,c\}\) and use the complete graph with weights \(w(ra)=1\), \(w(rb)=2\), \(w(rc)=10\), \(w(ab)=1\), \(w(ac)=2\), and \(w(bc)=3\). Take \(r\) as the root.
On the nonroot vertices \(\{a,b,c\}\), the two cheapest edges are \(ab\) of weight \(1\) and \(ac\) of weight \(2\). They connect all three vertices and form a tree, so the minimum spanning-tree weight is \(1+2=3\). The two cheapest root edges are \(ra\) of weight \(1\) and \(rb\) of weight \(2\), with total weight \(1+2=3\). Hence the minimum rooted one-tree has edges \(\{ab,ac,ra,rb\}\) and weight \(3+3=6\).
This one-tree is not a tour: \(\deg(a)=3\), since \(a\) is incident with \(ab\), \(ac\), and \(ra\); also \(\deg(c)=1\), since only \(ac\) is incident with \(c\). Its unique cycle is \(r,a,b,r\), while \(c\) is attached by the branch \(ac\).
Check: the one-tree has \(2\) edges in its tree on three nonroot vertices and \(2\) root edges, for \(4=n\) edges total. Its weight is \(w(ab)+w(ac)+w(ra)+w(rb)=1+2+1+2=6\). The three undirected tours (listed up to reversing direction) have weights \(r,a,b,c,r: 1+1+3+10=15\), \(r,a,c,b,r: 1+2+3+2=8\), and \(r,b,a,c,r: 2+1+2+10=15\). Thus the optimal tour costs \(8\), which is at least the minimum one-tree weight \(6\), but the minimum one-tree itself is not a tour.
The Choice of Root
The lower-bound theorem holds for every root, but the minimum one-tree weight can depend on which vertex is chosen as the root. The reason is that the tree part and the two-root-edge part change with the root. Each choice still gives a valid lower bound; the values need not agree.
Worked Example: Changing the Root Changes the Bound
Use the same complete weighted graph \(V=\{r,a,b,c\}\) from the previous example: \(w(ra)=1\), \(w(rb)=2\), \(w(rc)=10\), \(w(ab)=1\), \(w(ac)=2\), and \(w(bc)=3\). For root \(r\), the nonroot tree has weight \(1+2=3\), and the two cheapest root edges have weight \(1+2=3\). The minimum one-tree weight is therefore \(6\).
Now choose \(a\) as the root. The nonroot vertices are \(\{r,b,c\}\). Their edge weights are \(w(rb)=2\), \(w(bc)=3\), and \(w(rc)=10\). The two cheapest edges \(rb\) and \(bc\) connect all three vertices, so the minimum spanning-tree weight is \(2+3=5\). The root-\(a\) edges have weights \(w(ar)=1\), \(w(ab)=1\), and \(w(ac)=2\); the two cheapest distinct edges have total weight \(1+1=2\). Therefore the minimum one-tree with root \(a\) has weight \(5+2=7\).
Check: the root-\(a\) one-tree can use edges \(rb,bc,ar,ab\), with total weight \(2+3+1+1=7\). It has three edges in its nonroot tree and two edges at the root, as required. The minimum tour weight is \(8\), as computed in the previous example, so both root choices give lower bounds: \(6\le8\) and \(7\le8\). In this instance the root-\(a\) bound is larger, but it is still not the tour cost.
Common Pitfalls and Use of the Bound
Counting arbitrary cheap edges is not enough. In the first example, the two cheapest edges in the whole graph are \(bc\) of weight \(1\) and \(ab\) of weight \(2\), whose sum is \(3\). They are not root edges, so adding them as the required pair would not produce a rooted one-tree. The correct pair must be chosen from \(ra,rb,rc,rd\): the two least weights there are \(2\) and \(3\), giving \(5\). The correct one-tree minimum is consequently \(7+5=12\), not \(7+3=10\).
Do not require every nonroot degree to be two when constructing a one-tree. That condition would restrict the object to tours and remove the relaxation that makes the lower bound useful. Conversely, do not call a minimum one-tree a tour without checking all degrees. In the second example, the minimum one-tree has weight \(6\), but its degrees at \(a\) and \(c\) are \(3\) and \(1\), so it cannot be a Hamiltonian tour.
The one-tree bound is useful because it is obtained by two manageable optimization tasks: a spanning-tree computation away from the root, and a choice of two root edges. It supplies a certified benchmark: no tour can cost less than the computed minimum one-tree. A gap between that bound and a known tour cost does not prove that the tour is optimal; it only measures how much room remains between this lower bound and that tour.
Check Your Understanding
For each question, state the relevant root and distinguish the tree edges from the root edges.
- Why does deleting the two edges incident with the root from a Hamiltonian tour leave a spanning tree on the other \(n-1\) vertices?
- For root \(r\), suppose the minimum spanning-tree weight on the nonroot vertices is \(11\), and the two cheapest distinct root edges have weights \(3\) and \(5\). What is the minimum rooted one-tree weight?
- Can a rooted one-tree have a nonroot vertex of degree \(1\)? Explain why this does not contradict its connectivity.
- In the second worked example, identify the unique cycle of the minimum one-tree and the vertex attached as a branch.
- Does a lower bound of \(6\) and a known tour of weight \(8\) establish that the tour is optimal? Explain what the bound does establish.