4
$\begingroup$

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")

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks! I constructed a longer path based on the assumption. $\endgroup$ – user31899 Jun 9 '12 at 4:55
1
$\begingroup$

You might find these items of interest: http://web.archive.org/web/20100619094433/http://orion.math.iastate.edu/axenovic/Papers/Path-Transversals.pdf and http://www.math.uiuc.edu/~west/openp/pathtran.html

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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