Prove that the total distance is minimised (when travelling across the longest path)












4












$begingroup$


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



enter image description here



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










share|cite|improve this question











$endgroup$

















    4












    $begingroup$


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



    enter image description here



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










    share|cite|improve this question











    $endgroup$















      4












      4








      4





      $begingroup$


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



      enter image description here



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










      share|cite|improve this question











      $endgroup$




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



      enter image description here



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







      graphs graph-theory trees correctness-proof






      share|cite|improve this question















      share|cite|improve this question













      share|cite|improve this question




      share|cite|improve this question








      edited 4 hours ago







      rranjik

















      asked 9 hours ago









      rranjikrranjik

      1028




      1028






















          2 Answers
          2






          active

          oldest

          votes


















          4












          $begingroup$

          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.






          share|cite|improve this answer









          $endgroup$













          • $begingroup$
            Thanks David. The $d(x,y)$ you use is the shortest path between $x$ and $y$ isn't it ?! Shortest because once I'm done, I want to retract in the shortest possible way. And, the shortest path between any two vertices that is the greatest should be the diameter. I want to find the largest shortest distance because I want to minimise $L$.
            $endgroup$
            – rranjik
            6 hours ago








          • 1




            $begingroup$
            @rranjik Yes, $d(x,y)$ is distance. But you’re trying to minimise $L_{xy}$, so you need to maximise $d$.
            $endgroup$
            – David Richerby
            5 hours ago










          • $begingroup$
            Oops! Minimise $L_{xy}$ not $L$. $L$ is just a constant for the given graph as you mentioned. Thanks for clarifying.
            $endgroup$
            – rranjik
            5 hours ago





















          4












          $begingroup$

          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 $$begin{align}{sum_{ein E}t_ee}&=sum_{ein P}t_ee + sum_{ein Etext{ and }enotin P}t_ee\
          &=sum_{ein E}2e + sum_{ein P}(t_e-2)e + sum_{ein Etext{ and }enotin P}(t_e-2)e\
          &gesum_{ein E}2e + sum_{ein P}(t_e-2)e \
          &gesum_{ein E}2e - sum_{ein P}e \
          &gesum_{ein E}2e - text{ diameter of } T \
          end{align}$$



          The other part of the proof is to show the journey can be as short as $displaystyle{sum_{ein E}2e - sum_{ein P}e}$ 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$.






          share|cite|improve this answer











          $endgroup$













          • $begingroup$
            @Apass.Jack Thanks for your time. I appreciate it. This is very rigorous as you mentioned. I was reading it all this time trying to understand. (I'm not really good at understanding a lot of math). Could you please explain the last line of the proof where we use $sum_{ein P}e ge text{ diameter of } T$ ? Isn't any path in the tree always lesser than or equal to the diameter. So the sum of the edges in $P$ should be at most the diameter right ?
            $endgroup$
            – rranjik
            5 hours ago










          • $begingroup$
            @rranjik Exactly.
            $endgroup$
            – Apass.Jack
            5 hours ago










          • $begingroup$
            @Apass.Jack I'm sorry. I still could not understand. I ask, isn't $sum_{ein P}e le text{ diameter of } T$ always ? Apparently, we are using it the other way around. Could you please explain a little more ?
            $endgroup$
            – rranjik
            5 hours ago










          • $begingroup$
            @rranjik Did you notice there is negative sign? $-sum_{ein P}e ge -text{ diameter of } T$
            $endgroup$
            – Apass.Jack
            5 hours ago












          • $begingroup$
            Uh-oh sorry! Thank you so much.
            $endgroup$
            – rranjik
            5 hours ago











          Your Answer





          StackExchange.ifUsing("editor", function () {
          return StackExchange.using("mathjaxEditing", function () {
          StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
          StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
          });
          });
          }, "mathjax-editing");

          StackExchange.ready(function() {
          var channelOptions = {
          tags: "".split(" "),
          id: "419"
          };
          initTagRenderer("".split(" "), "".split(" "), channelOptions);

          StackExchange.using("externalEditor", function() {
          // Have to fire editor after snippets, if snippets enabled
          if (StackExchange.settings.snippets.snippetsEnabled) {
          StackExchange.using("snippets", function() {
          createEditor();
          });
          }
          else {
          createEditor();
          }
          });

          function createEditor() {
          StackExchange.prepareEditor({
          heartbeatType: 'answer',
          autoActivateHeartbeat: false,
          convertImagesToLinks: false,
          noModals: true,
          showLowRepImageUploadWarning: true,
          reputationToPostImages: null,
          bindNavPrevention: true,
          postfix: "",
          imageUploader: {
          brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
          contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
          allowUrls: true
          },
          onDemand: true,
          discardSelector: ".discard-answer"
          ,immediatelyShowMarkdownHelp:true
          });


          }
          });














          draft saved

          draft discarded


















          StackExchange.ready(
          function () {
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f105534%2fprove-that-the-total-distance-is-minimised-when-travelling-across-the-longest-p%23new-answer', 'question_page');
          }
          );

          Post as a guest















          Required, but never shown

























          2 Answers
          2






          active

          oldest

          votes








          2 Answers
          2






          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes









          4












          $begingroup$

          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.






          share|cite|improve this answer









          $endgroup$













          • $begingroup$
            Thanks David. The $d(x,y)$ you use is the shortest path between $x$ and $y$ isn't it ?! Shortest because once I'm done, I want to retract in the shortest possible way. And, the shortest path between any two vertices that is the greatest should be the diameter. I want to find the largest shortest distance because I want to minimise $L$.
            $endgroup$
            – rranjik
            6 hours ago








          • 1




            $begingroup$
            @rranjik Yes, $d(x,y)$ is distance. But you’re trying to minimise $L_{xy}$, so you need to maximise $d$.
            $endgroup$
            – David Richerby
            5 hours ago










          • $begingroup$
            Oops! Minimise $L_{xy}$ not $L$. $L$ is just a constant for the given graph as you mentioned. Thanks for clarifying.
            $endgroup$
            – rranjik
            5 hours ago


















          4












          $begingroup$

          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.






          share|cite|improve this answer









          $endgroup$













          • $begingroup$
            Thanks David. The $d(x,y)$ you use is the shortest path between $x$ and $y$ isn't it ?! Shortest because once I'm done, I want to retract in the shortest possible way. And, the shortest path between any two vertices that is the greatest should be the diameter. I want to find the largest shortest distance because I want to minimise $L$.
            $endgroup$
            – rranjik
            6 hours ago








          • 1




            $begingroup$
            @rranjik Yes, $d(x,y)$ is distance. But you’re trying to minimise $L_{xy}$, so you need to maximise $d$.
            $endgroup$
            – David Richerby
            5 hours ago










          • $begingroup$
            Oops! Minimise $L_{xy}$ not $L$. $L$ is just a constant for the given graph as you mentioned. Thanks for clarifying.
            $endgroup$
            – rranjik
            5 hours ago
















          4












          4








          4





          $begingroup$

          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.






          share|cite|improve this answer









          $endgroup$



          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.







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          answered 7 hours ago









          David RicherbyDavid Richerby

          68.3k15103194




          68.3k15103194












          • $begingroup$
            Thanks David. The $d(x,y)$ you use is the shortest path between $x$ and $y$ isn't it ?! Shortest because once I'm done, I want to retract in the shortest possible way. And, the shortest path between any two vertices that is the greatest should be the diameter. I want to find the largest shortest distance because I want to minimise $L$.
            $endgroup$
            – rranjik
            6 hours ago








          • 1




            $begingroup$
            @rranjik Yes, $d(x,y)$ is distance. But you’re trying to minimise $L_{xy}$, so you need to maximise $d$.
            $endgroup$
            – David Richerby
            5 hours ago










          • $begingroup$
            Oops! Minimise $L_{xy}$ not $L$. $L$ is just a constant for the given graph as you mentioned. Thanks for clarifying.
            $endgroup$
            – rranjik
            5 hours ago




















          • $begingroup$
            Thanks David. The $d(x,y)$ you use is the shortest path between $x$ and $y$ isn't it ?! Shortest because once I'm done, I want to retract in the shortest possible way. And, the shortest path between any two vertices that is the greatest should be the diameter. I want to find the largest shortest distance because I want to minimise $L$.
            $endgroup$
            – rranjik
            6 hours ago








          • 1




            $begingroup$
            @rranjik Yes, $d(x,y)$ is distance. But you’re trying to minimise $L_{xy}$, so you need to maximise $d$.
            $endgroup$
            – David Richerby
            5 hours ago










          • $begingroup$
            Oops! Minimise $L_{xy}$ not $L$. $L$ is just a constant for the given graph as you mentioned. Thanks for clarifying.
            $endgroup$
            – rranjik
            5 hours ago


















          $begingroup$
          Thanks David. The $d(x,y)$ you use is the shortest path between $x$ and $y$ isn't it ?! Shortest because once I'm done, I want to retract in the shortest possible way. And, the shortest path between any two vertices that is the greatest should be the diameter. I want to find the largest shortest distance because I want to minimise $L$.
          $endgroup$
          – rranjik
          6 hours ago






          $begingroup$
          Thanks David. The $d(x,y)$ you use is the shortest path between $x$ and $y$ isn't it ?! Shortest because once I'm done, I want to retract in the shortest possible way. And, the shortest path between any two vertices that is the greatest should be the diameter. I want to find the largest shortest distance because I want to minimise $L$.
          $endgroup$
          – rranjik
          6 hours ago






          1




          1




          $begingroup$
          @rranjik Yes, $d(x,y)$ is distance. But you’re trying to minimise $L_{xy}$, so you need to maximise $d$.
          $endgroup$
          – David Richerby
          5 hours ago




          $begingroup$
          @rranjik Yes, $d(x,y)$ is distance. But you’re trying to minimise $L_{xy}$, so you need to maximise $d$.
          $endgroup$
          – David Richerby
          5 hours ago












          $begingroup$
          Oops! Minimise $L_{xy}$ not $L$. $L$ is just a constant for the given graph as you mentioned. Thanks for clarifying.
          $endgroup$
          – rranjik
          5 hours ago






          $begingroup$
          Oops! Minimise $L_{xy}$ not $L$. $L$ is just a constant for the given graph as you mentioned. Thanks for clarifying.
          $endgroup$
          – rranjik
          5 hours ago













          4












          $begingroup$

          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 $$begin{align}{sum_{ein E}t_ee}&=sum_{ein P}t_ee + sum_{ein Etext{ and }enotin P}t_ee\
          &=sum_{ein E}2e + sum_{ein P}(t_e-2)e + sum_{ein Etext{ and }enotin P}(t_e-2)e\
          &gesum_{ein E}2e + sum_{ein P}(t_e-2)e \
          &gesum_{ein E}2e - sum_{ein P}e \
          &gesum_{ein E}2e - text{ diameter of } T \
          end{align}$$



          The other part of the proof is to show the journey can be as short as $displaystyle{sum_{ein E}2e - sum_{ein P}e}$ 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$.






          share|cite|improve this answer











          $endgroup$













          • $begingroup$
            @Apass.Jack Thanks for your time. I appreciate it. This is very rigorous as you mentioned. I was reading it all this time trying to understand. (I'm not really good at understanding a lot of math). Could you please explain the last line of the proof where we use $sum_{ein P}e ge text{ diameter of } T$ ? Isn't any path in the tree always lesser than or equal to the diameter. So the sum of the edges in $P$ should be at most the diameter right ?
            $endgroup$
            – rranjik
            5 hours ago










          • $begingroup$
            @rranjik Exactly.
            $endgroup$
            – Apass.Jack
            5 hours ago










          • $begingroup$
            @Apass.Jack I'm sorry. I still could not understand. I ask, isn't $sum_{ein P}e le text{ diameter of } T$ always ? Apparently, we are using it the other way around. Could you please explain a little more ?
            $endgroup$
            – rranjik
            5 hours ago










          • $begingroup$
            @rranjik Did you notice there is negative sign? $-sum_{ein P}e ge -text{ diameter of } T$
            $endgroup$
            – Apass.Jack
            5 hours ago












          • $begingroup$
            Uh-oh sorry! Thank you so much.
            $endgroup$
            – rranjik
            5 hours ago
















          4












          $begingroup$

          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 $$begin{align}{sum_{ein E}t_ee}&=sum_{ein P}t_ee + sum_{ein Etext{ and }enotin P}t_ee\
          &=sum_{ein E}2e + sum_{ein P}(t_e-2)e + sum_{ein Etext{ and }enotin P}(t_e-2)e\
          &gesum_{ein E}2e + sum_{ein P}(t_e-2)e \
          &gesum_{ein E}2e - sum_{ein P}e \
          &gesum_{ein E}2e - text{ diameter of } T \
          end{align}$$



          The other part of the proof is to show the journey can be as short as $displaystyle{sum_{ein E}2e - sum_{ein P}e}$ 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$.






          share|cite|improve this answer











          $endgroup$













          • $begingroup$
            @Apass.Jack Thanks for your time. I appreciate it. This is very rigorous as you mentioned. I was reading it all this time trying to understand. (I'm not really good at understanding a lot of math). Could you please explain the last line of the proof where we use $sum_{ein P}e ge text{ diameter of } T$ ? Isn't any path in the tree always lesser than or equal to the diameter. So the sum of the edges in $P$ should be at most the diameter right ?
            $endgroup$
            – rranjik
            5 hours ago










          • $begingroup$
            @rranjik Exactly.
            $endgroup$
            – Apass.Jack
            5 hours ago










          • $begingroup$
            @Apass.Jack I'm sorry. I still could not understand. I ask, isn't $sum_{ein P}e le text{ diameter of } T$ always ? Apparently, we are using it the other way around. Could you please explain a little more ?
            $endgroup$
            – rranjik
            5 hours ago










          • $begingroup$
            @rranjik Did you notice there is negative sign? $-sum_{ein P}e ge -text{ diameter of } T$
            $endgroup$
            – Apass.Jack
            5 hours ago












          • $begingroup$
            Uh-oh sorry! Thank you so much.
            $endgroup$
            – rranjik
            5 hours ago














          4












          4








          4





          $begingroup$

          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 $$begin{align}{sum_{ein E}t_ee}&=sum_{ein P}t_ee + sum_{ein Etext{ and }enotin P}t_ee\
          &=sum_{ein E}2e + sum_{ein P}(t_e-2)e + sum_{ein Etext{ and }enotin P}(t_e-2)e\
          &gesum_{ein E}2e + sum_{ein P}(t_e-2)e \
          &gesum_{ein E}2e - sum_{ein P}e \
          &gesum_{ein E}2e - text{ diameter of } T \
          end{align}$$



          The other part of the proof is to show the journey can be as short as $displaystyle{sum_{ein E}2e - sum_{ein P}e}$ 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$.






          share|cite|improve this answer











          $endgroup$



          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 $$begin{align}{sum_{ein E}t_ee}&=sum_{ein P}t_ee + sum_{ein Etext{ and }enotin P}t_ee\
          &=sum_{ein E}2e + sum_{ein P}(t_e-2)e + sum_{ein Etext{ and }enotin P}(t_e-2)e\
          &gesum_{ein E}2e + sum_{ein P}(t_e-2)e \
          &gesum_{ein E}2e - sum_{ein P}e \
          &gesum_{ein E}2e - text{ diameter of } T \
          end{align}$$



          The other part of the proof is to show the journey can be as short as $displaystyle{sum_{ein E}2e - sum_{ein P}e}$ 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$.







          share|cite|improve this answer














          share|cite|improve this answer



          share|cite|improve this answer








          edited 6 hours ago

























          answered 7 hours ago









          Apass.JackApass.Jack

          12.6k1939




          12.6k1939












          • $begingroup$
            @Apass.Jack Thanks for your time. I appreciate it. This is very rigorous as you mentioned. I was reading it all this time trying to understand. (I'm not really good at understanding a lot of math). Could you please explain the last line of the proof where we use $sum_{ein P}e ge text{ diameter of } T$ ? Isn't any path in the tree always lesser than or equal to the diameter. So the sum of the edges in $P$ should be at most the diameter right ?
            $endgroup$
            – rranjik
            5 hours ago










          • $begingroup$
            @rranjik Exactly.
            $endgroup$
            – Apass.Jack
            5 hours ago










          • $begingroup$
            @Apass.Jack I'm sorry. I still could not understand. I ask, isn't $sum_{ein P}e le text{ diameter of } T$ always ? Apparently, we are using it the other way around. Could you please explain a little more ?
            $endgroup$
            – rranjik
            5 hours ago










          • $begingroup$
            @rranjik Did you notice there is negative sign? $-sum_{ein P}e ge -text{ diameter of } T$
            $endgroup$
            – Apass.Jack
            5 hours ago












          • $begingroup$
            Uh-oh sorry! Thank you so much.
            $endgroup$
            – rranjik
            5 hours ago


















          • $begingroup$
            @Apass.Jack Thanks for your time. I appreciate it. This is very rigorous as you mentioned. I was reading it all this time trying to understand. (I'm not really good at understanding a lot of math). Could you please explain the last line of the proof where we use $sum_{ein P}e ge text{ diameter of } T$ ? Isn't any path in the tree always lesser than or equal to the diameter. So the sum of the edges in $P$ should be at most the diameter right ?
            $endgroup$
            – rranjik
            5 hours ago










          • $begingroup$
            @rranjik Exactly.
            $endgroup$
            – Apass.Jack
            5 hours ago










          • $begingroup$
            @Apass.Jack I'm sorry. I still could not understand. I ask, isn't $sum_{ein P}e le text{ diameter of } T$ always ? Apparently, we are using it the other way around. Could you please explain a little more ?
            $endgroup$
            – rranjik
            5 hours ago










          • $begingroup$
            @rranjik Did you notice there is negative sign? $-sum_{ein P}e ge -text{ diameter of } T$
            $endgroup$
            – Apass.Jack
            5 hours ago












          • $begingroup$
            Uh-oh sorry! Thank you so much.
            $endgroup$
            – rranjik
            5 hours ago
















          $begingroup$
          @Apass.Jack Thanks for your time. I appreciate it. This is very rigorous as you mentioned. I was reading it all this time trying to understand. (I'm not really good at understanding a lot of math). Could you please explain the last line of the proof where we use $sum_{ein P}e ge text{ diameter of } T$ ? Isn't any path in the tree always lesser than or equal to the diameter. So the sum of the edges in $P$ should be at most the diameter right ?
          $endgroup$
          – rranjik
          5 hours ago




          $begingroup$
          @Apass.Jack Thanks for your time. I appreciate it. This is very rigorous as you mentioned. I was reading it all this time trying to understand. (I'm not really good at understanding a lot of math). Could you please explain the last line of the proof where we use $sum_{ein P}e ge text{ diameter of } T$ ? Isn't any path in the tree always lesser than or equal to the diameter. So the sum of the edges in $P$ should be at most the diameter right ?
          $endgroup$
          – rranjik
          5 hours ago












          $begingroup$
          @rranjik Exactly.
          $endgroup$
          – Apass.Jack
          5 hours ago




          $begingroup$
          @rranjik Exactly.
          $endgroup$
          – Apass.Jack
          5 hours ago












          $begingroup$
          @Apass.Jack I'm sorry. I still could not understand. I ask, isn't $sum_{ein P}e le text{ diameter of } T$ always ? Apparently, we are using it the other way around. Could you please explain a little more ?
          $endgroup$
          – rranjik
          5 hours ago




          $begingroup$
          @Apass.Jack I'm sorry. I still could not understand. I ask, isn't $sum_{ein P}e le text{ diameter of } T$ always ? Apparently, we are using it the other way around. Could you please explain a little more ?
          $endgroup$
          – rranjik
          5 hours ago












          $begingroup$
          @rranjik Did you notice there is negative sign? $-sum_{ein P}e ge -text{ diameter of } T$
          $endgroup$
          – Apass.Jack
          5 hours ago






          $begingroup$
          @rranjik Did you notice there is negative sign? $-sum_{ein P}e ge -text{ diameter of } T$
          $endgroup$
          – Apass.Jack
          5 hours ago














          $begingroup$
          Uh-oh sorry! Thank you so much.
          $endgroup$
          – rranjik
          5 hours ago




          $begingroup$
          Uh-oh sorry! Thank you so much.
          $endgroup$
          – rranjik
          5 hours ago


















          draft saved

          draft discarded




















































          Thanks for contributing an answer to Computer Science Stack Exchange!


          • Please be sure to answer the question. Provide details and share your research!

          But avoid



          • Asking for help, clarification, or responding to other answers.

          • Making statements based on opinion; back them up with references or personal experience.


          Use MathJax to format equations. MathJax reference.


          To learn more, see our tips on writing great answers.




          draft saved


          draft discarded














          StackExchange.ready(
          function () {
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f105534%2fprove-that-the-total-distance-is-minimised-when-travelling-across-the-longest-p%23new-answer', 'question_page');
          }
          );

          Post as a guest















          Required, but never shown





















































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown

































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown







          Popular posts from this blog

          GameSpot

          日野市

          Tu-95轟炸機