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 a center of a tree (or if not much harder, of any graph) lies on the longest path.

(I encountered this when I was reading an alternative proof for the property :"a tree has at most two centers")

share|improve this question
add comment

2 Answers

I think it goes like this. Let $c$ be the center. Let $P$ be a longest path. If $c$ is not on $P$ then there is a path from $c$ to some vertex $v$ on $P$ (I'm assuming the graph is connected, else I think the whole concept of center doesn't apply). Now I think you can prove that $v$ is more central than $c$, that is, that if the distance from $v$ to the farthest point exceeds the distance from $c$ to its farthest point then $c$ is on a path at least as long as $P$, contradiction.

I acknowledge that I have left some details to fill in.

share|improve this answer
    
Thanks! I constructed a longer path based on the assumption. –  user31899 Jun 9 '12 at 4:55
add comment

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.