1
$\begingroup$

Prove that in every tree, any two paths with maximum length have a node in common. This is not true if we consider two maximal (i.e. non-extendable) paths.

What does this even mean?

  • 0
    @Asaf Since your comment seems to have addressed all of OP's concerns, could you post it as an answer, so as to remove this question from the unanswered queue?2013-05-22

1 Answers 1

1

If we have a path we can measure its length (how many vertices, or edges, it goes through).

The length is a natural number, the question asks to show that given two paths which have the longest possible length (i.e. the length is maximum possible) then they have a common node; however if we only take maximal paths (which are paths which we just cannot extend any further) then it might not be true if the length of these paths is not the maximum from the first part.