goodar2006 wrote: prove that if graph $G$ is a tree, then there is a vertex that is common between all of the longest paths.

Click to reveal hidden text

@ashkan

We know that in any connected graph every three longest paths have a common vertex. Take three longest paths $p_1,p_2,p_3$ such that $S:=p_1\cap p_2\cap p_3$ is minimal. We know by the above$S\not=\emptyset$. As $G$ is a tree, the induced graph $\langle G\rangle_S$ must be a path $v_1v_2...v_k$, and there are $n_1,n_2$ such that each of $p_1,p_2,p_3$ consists of a path of length $n_1$, then $v_1v_2...v_k$, then a path of length $n_2$. And this must obviously be also the case for all other longest paths, by the minimality of $S$ and by the maximality of the paths. So $S\subset p$ for any longest path $p$.

goodar2006 wrote: prove that if graph $G$ is a tree, then there is a vertex that is common between all of the longest paths. From http://www.artofproblemsolving.com/Forum/viewtopic.php?f=73&t=230639 , we know that if $S$ is a finite set of subtrees of a given tree $G$ such that any two subtrees in $S$ intersect, then all subtrees in $S$ intersect. Apply this to $S$ being the set of all longest paths of $G$. (We view paths of $G$ as subtrees of $G$.) The only thing we have to check is that any two longest paths of $G$ intersect. In fact, let $a_1a_2...a_n$ and $b_1b_2...b_n$ be two longest paths of $G$. Let $a_i$ be the vertex of the path $a_1a_2...a_n$ closest to the path $b_1b_2...b_n$, and let $b_j$ be the vertex of the path $b_1b_2...b_n$ closest to the path $a_1a_2...a_n$. Let $c_1c_2...c_k$ be the path between $a_i$ and $b_j$, with $c_1=a_i$ and $c_k=b_j$. If $k=1$, then $a_i=c_1=c_k=b_j$, so that our paths $a_1a_2...a_n$ and $b_1b_2...b_n$ intersect and we are done. Now consider the case $k>1$. Then, the path $c_1c_2...c_k$ intersects the paths $a_1a_2...a_n$ and $b_1b_2...b_n$ only at the points $c_1$ and $c_k$ (this is easy to see using the definition of $a_i$ and $b_j$). Now, at least one of the paths $a_1a_2...a_ic_2c_3...c_{k-1}b_jb_{j+1}...b_n$ and $b_1b_2...b_jc_{k-1}c_{k-2}...c_2a_ia_{i+1}...a_n$ has length $>n$ (in fact, the first of them has length $i+\left(k-2\right)+\left(n-j\right)\geq i+\left(n-j\right)$, and the second has length $j+\left(k-2\right)+\left(n-i\right)\geq j+\left(n-i\right)$). The interesting part is proving http://www.artofproblemsolving.com/Forum/viewtopic.php?f=73&t=230639 ... (Or, actually, writing up the proof. Finding it isn't hard, and at least for a finite tree you won't need any geometric group theory.)