1. ## Graph Theory Proof

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?

2. ## Re: Graph Theory Proof

Originally Posted by elemental
Distance between two vertices is length of shortest path that connects them.
What are the defining characteristics of a tree ?

A tree is a connected simple graph that has no cycles.

Because the graph is connected there is a path between any two vertices. RIGHT?

Because the graph is acyclic, is that path unique?

3. ## Re: Graph Theory Proof

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.

4. ## Re: Graph Theory Proof

Originally Posted by elemental
Yes I agree that every path between two vertices is unique.
If that path is unique, then is it not both the longest and the shortest path ?

5. ## Re: Graph Theory Proof

Yes but I am asked to prove that the path between X and Y is the longest path of any path at all in the entire tree.

6. ## Re: Graph Theory Proof

Originally Posted by elemental
Yes but I am asked to prove that the path between X and Y is the longest path of any path at all in the entire tree.
Do you know what the word unique means ?

7. ## Re: Graph Theory Proof

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.

8. ## Re: Graph Theory Proof

Originally Posted by elemental
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.
Originally Posted by elemental
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.
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.

9. ## Re: Graph Theory Proof

Thanks. I solved it yesterday. I first rooted the tree at V and then considered the longest path in the tree, assumed it was longer than X-->Y. Then I broke it up into cases based on common ancestors to yield contradictions.