Mryntu

Here is the problem: Given a tree $T$, I need to visit every node in the tree once. I can start and end anywhere I want. I would like to travel the least distance possible when doing so. I don't have to return where I started.

As my specification is not really clear I made up an example: Consider the graph (which is a tree here - undirected weighted acyclic graph) to have nodes as cities and edges as roads between cities. I need to deliver something to every city (visit every node at least once). I can start from any city and end at any city that I choose to.

I read the following result. Find the two cities in the graph that are the farthest apart (call them $c1$ and $c2$). Start from one of them ($c1$ or $c2$), visit every other city along the way until I reach ($c2$ or $c1$). This minimises the total distance to travel.

How should I prove that this is the minimum distance ?

I attempted the following. I have the final route and I call edges, $m_1, m_2, ..., m_i$ and $e_1, e_2, ..., e_j$. Where $m_1, m_2, ..., m_i$ are the edges along the cities that are the farthest apart ($c1$ and $c2$) and $e_1, e_2, ..., e_j$ are everything else in the graph. As I start from $c1$, I travel along edges labelled m exactly once and everything else labelled e is a digression and go back and forth twice on those edges, before I reach $c2$.

We know that $m_1, m_2, ..., m_i$ and $e_1, e_2, ..., e_j$ taken together include all the edges on the graph (as it is a tree, there's only a unique path between every two nodes). So the distance I travel could be given as $2(e_1 + e_2 + .... + e_j) + (m_1 + m_2 + ... + m_i)$.

I need to prove that this sum is less than every other route that I can take to reach all the cities. My intuition says that this has to be the shortest route. I feel that have to use the fact that $(m_1 + m_2 + ... + m_i)$ is the maximum between any two nodes in the graph somehow (is that called the diameter ?), and arrive at a contradiction.

This is the kind of picture I have in my mind (red edges are in ($m_1, m_2, ..., m_i$) and the grey ones are everything else),

That graph is still a tree (please ignore the arrow head in the edges that show how I decide to travel). I don't to where to go from here. I would appreciate a proof that is simple to understand (This is not a homework or anything related to coursework.)

Let $x$ be a vertex of your tree and consider a shortest route that visits every vertex and returns to $x$. It's easy to see that, regardless of the choice of $x$, any minimal route walks along every edge exactly twice: it must use each edge at least twice, or it wouldn't be able to get back to $x$; if it uses an edge more than twice, you can rearrange to avoid the backtracking. Therefore, all such minimal routes have the same length, regardless of the choice of $x$. Call that length $L$ (which is $2(n-1)$ if the tree is unweighted and there are $n$ vertices, but this isn't important).

Now, given a minimal route from $x$, let $y$ be the last vertex to be visited for the first time (i.e., the vertex which, when you first visit it, you say "Aha, now I've been to every vertex!"). The minimal route visits every vertex on its way from $x$ to $y$, and then returns immediately to $x$ along the unique shortest path. Let $L_xy$ be the length of the walk taken from $x$ to $y$. We know that $L=L_xy+d(x,y)$, and $L$ and $d(x,y)$ don't depend on how we got to $y$, so $L_x,y$ also doesn't depend on the route and we can say that $L_xy$ is the length of any minimal walk from $x$ to $y$ that visits every vertex.

The vertex $y$ must be a leaf: if it wasn't, when you first visited $y$, you wouldn't have visited any of the vertices "beyond" it. Further, for any leaf $z$ of the tree, there are minimal routes from $x$ back to itself such that $z$ is the last vertex visited for the first time: let $v_1v_2dots v_t$ be the path from $v_1=x$ to $z=v_t$ and don't go to $v_i+1$ until you've already visited every other descendant of $v_i$.

So, to get the longest walk from $x$ that visits every vertex, pick a route whose $y$ is the leaf at greatest distance from $x$. None of the above depends on which vertex was chosen as $x$, $L_xy=L-d(x,y)$ is minimized by choosing $x$ and $y$ to be the vertices at greatest possible distance in the tree, which are both leaves.

Here is a proof rigorous enough that should be easy enough to understand as well.

Let $T=(V,E)$. Let $j$ be a journey that passes every city, starting at city $s$ and finishing at city $f$. Let $t_e$ is the number of times $j$ goes through edge $e$. Let $P$ be the unique path from $s$ to $f$.

Claim 1: $t_ege 1$.

Proof: If we remove edge $e$ from $T$, $T$ is separated into two trees that are disconnected to each other. If $t_enotge1$, i.e., $j$ does not include $e$, that means $j$ is disconnected, which is false.

Claim 2: $t_ege 2$ if $enotin P$.

Proof. Let $enotin P$. If we remove edge $e$ from $T$, $T$ is separated into two smaller trees that are disconnected to each other. Denote those two trees $T_1$ and $T_2$. Since $P$ is connected, $P$ is in $T_1$ entirely or $T_2$ entirely. That means both $s$ and $f$ are in $T_1$ or both are in $T_2$. Starting at $s$ in one of the smaller trees, $j$ must go to the other smaller tree through $e$ before returning to $f$ through $e$ again.

The total distance of $j$ is $$beginalignsum_ein Et_ee&=sum_ein Pt_ee + sum_ein Etext and enotin Pt_ee\
&=sum_ein E2e + sum_ein P(t_e-2)e + sum_ein Etext and enotin P(t_e-2)e\
&gesum_ein E2e + sum_ein P(t_e-2)e \
&gesum_ein E2e - sum_ein Pe \
&gesum_ein E2e - text diameter of T \
endalign$$

The other part of the proof is to show the journey can be as short as $displaystylesum_ein E2e - sum_ein Pe$ for any path $P$, as indicated by the picture in the question. We can prove by induction on $n$, the number of nodes that is not on $P$. The base case when $n=0$ is clear. For the induction step, we can find a leaf that is not in $P$. (Pick any edge not in $P$, whose removal splits $T$ into two smaller trees. Pick any leaf in the smaller tree that does not contain $P$.) Then we can extend a journey that misses that leaf by inserting into that journey an excursion that goes to that leaf and then returns back.

Here is a related exercise.

Exercise. Prove the following algorithm finds a diameter of a given tree.

1. Let $u$ be a node.


2. Find $v$, one of the farthest nodes from $u$.


3. Find $w$, one of the farthest nodes from $v$.


4. return the path from $v$ to $w$.