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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

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|cite|improve this answer
Thanks! I constructed a longer path based on the assumption. – user31899 Jun 9 '12 at 4:55

Your Answer


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.