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