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

2 Answers 2

4

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.

  • 0
    Thanks! I constructed a longer path based on the assumption.2012-06-09
1

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