Results 1 to 9 of 9

Math Help - Graph Theory Proof

  1. #1
    Junior Member
    Joined
    Jul 2010
    From
    NJ
    Posts
    68

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,959
    Thanks
    1781
    Awards
    1

    Re: Graph Theory Proof

    Quote Originally Posted by elemental View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jul 2010
    From
    NJ
    Posts
    68

    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.
    Last edited by elemental; December 14th 2013 at 04:32 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,959
    Thanks
    1781
    Awards
    1

    Re: Graph Theory Proof

    Quote Originally Posted by elemental View Post
    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 ?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Jul 2010
    From
    NJ
    Posts
    68

    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.
    Last edited by elemental; December 14th 2013 at 07:14 PM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,959
    Thanks
    1781
    Awards
    1

    Re: Graph Theory Proof

    Quote Originally Posted by elemental View Post
    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 ?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Jul 2010
    From
    NJ
    Posts
    68

    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,959
    Thanks
    1781
    Awards
    1

    Re: Graph Theory Proof

    Quote Originally Posted by elemental View Post
    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.
    Quote Originally Posted by elemental View Post
    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.
    Last edited by Plato; December 15th 2013 at 11:38 AM.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Jul 2010
    From
    NJ
    Posts
    68

    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof help need graph theory - Please !
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 24th 2012, 08:21 AM
  2. Graph Theory Proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 4th 2011, 01:16 AM
  3. graph theory proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 12th 2010, 12:00 AM
  4. Graph theory: proof
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: October 29th 2009, 01:00 PM
  5. Graph theory proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 26th 2009, 10:01 PM

Search Tags


/mathhelpforum @mathhelpforum