A tree is defined as a connected, undirected graph without any cycle. It is

obvious that there is a single, unique path between any two vertices in a tree. Let $T=(V,E)$ be

a tree and let $(u,v)$ be the length of the path between $u$ and $v.$ We aim to design an algorithm

to find the length of the longest path in $T,$ i$.$e$.,ma{x}_{u,\text{v}\text{i}\text{n}\text{V}}(u,v).$ If $(u^{\text{'}},v^{\text{'}})$ reaches this maximum,

i$.$e$.,(u^{\text{'}},v^{\text{'}})=ma{x}_{u,\text{v}\text{i}\text{n}\text{V}}(u,v),$ we say $(u^{\text{'}},v^{\text{'}})$ forms a furthest pair. Note that $T$ may contain

multiple furthest pairs.

a$.$ For any vertex uinV, we say $v^{\text{'}}$ is the furthest vertex to $u,$ if $(u,v^{\text{'}})=$

$ma{x}_{\text{v}\text{i}\text{n}\text{V}}(u,v).$ Prove that, for any vertex uinV with $v^{\text{'}}$ being $($any one of$)$ its further vertex,

there must exist vertex $u^{\text{'}}$ such that $(u^{\text{'}},v^{\text{'}})$ is one furthest pair of $T.$

b$.$ Given $T,$ design an algorithm to find a further pair and analyze its running time.

Your algorithm should run in $O(|V|+|E|)$ time. $($Hint: consider using the results of part $($a$)$

and BFS$.)$