You are given a network G  (V,A) where |V|  n, d(i, j) is the length of edge (i, j ) and a specified vertex a ∈ V . One service unit is located at a and has to visit each vertex in V so that total waiting time of all vertices is as small as possible. Assume the waiting time of a vertex is proportional to the total distance traveled by the server from a to the vertex. The total waiting time

(summed up over all customers) is then:

(n − 1)d

(a, 2) + (n − 2)d(2, 3) + (n − 3)d(3, 4)+· · ·+d(n − 1, n).

The Delivery Man Problem (DMP) is the problem of determining the tour that minimizes the total waiting time.

Assume that G is a tree with d(i, j )  1 for every (i, j ) ∈ A. Show that any tour that follows a depth-first search starting from a is optimal.