Distance between two vertices is length of shortest path that connects them.
Consider a vertex in a tree, call it V. Pick the (or one of the) vertex in the tree that is farthest from V in terms of distance, call it X. Now pick the vertex (or one of the) vertex in the tree that is farthest from X in terms of distance, call it Y. Show that the shortest path from X to Y is the longest, or one of the longest, shortest path in the tree.
I have a few approaches but they all call for many cases. You can try contradiction after you build your tree, or try rooting your tree at V, but neither of these is that pretty... any innovative approaches?
Yes I agree that every path between two vertices is unique.
So we know that path from X to Y is equal to or longer than path from V to X. If the paths share no vertices in common, then that's a contradiction since then our choice of X would have been Y to start with... We also know that if the path from X to Y is part of the longest path on the tree, then Y must be an endpoint of the longest path (if not it leads to the same contradiction)
But I am stuck here. The paths (V to X and X to Z) have some node in common (other than X) at least is all I know, but I can't make any more leaps from here.
Yes, but the question is asking to prove that the path length between X and Y is equal to the diameter of the tree. I understand that there is a unique path between X and Y, in that there is only one path to take to get from X to Y. But that doesn't necessarily mean that the length of this path is the diameter of the tree.
So if X is the farthest node from some random node V, and Y is the farthest node from X, we are asked to prove that the path from X to Y is longer than or as long as any path between any two vertices in the tree. I don't see how simply observing that every path between vertices is unique helps prove that X --> Y gives the maximal path length.
Yesterday I gave up trying to get you to think through this question, went to bed.
Using your notation, If the tree has more that one vertex then V not equal X.
It is possible that V=Y. In which case one can argue that the path from X-V is the longest in the tree.
Now if V is not Y then X-V-Y. In which case one can argue that the path from X-Y is the longest in the tree.