Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
3  
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. –  Asaf Karagila Mar 25 '12 at 23:01
    
thanks this is very helpful –  Jean Mar 25 '12 at 23:37
    
@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? –  Lord_Farin May 22 '13 at 20:52

1 Answer 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.