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.)