# Finding middle vertex of tree

"Given a graph G, the remoteness of a vertex v is the distance from v to the vertex u that is farthest from v in G. That is, the shortest path from v to u is as long as possible. A vertex of G with the smallest remoteness is called a middle vertex of G" Find the middle on O(n+m) where n,m are the number of vertices and edges respectively

I have this one idea and was wondering if it is valid: Start with the tree, remove all leaves on the tree. Repeat this until we have either one vertex left or we have to vertices joined by an edge. These vertices will have the shortest longest path. As these 2/1 vertices will be on the longest path/diameter of the graph and be in the middle of it. So these are middle vertices. I have applied this to some example trees and got the correct answer. Is it valid? Thanks

• You talk about graphs and trees. Which is it? Commented May 8 at 11:48
• Also the algorithm that you describe does not seem to be in $\mathcal{O}(n + m)$. Commented May 8 at 11:49
• @Nathaniel oh does it not? My professor shared a solution to a different question using the same process and stated the run time is that. And it's about trees Commented May 8 at 12:00

• find a maximum depth leaf $$u$$
• find the leaf $$v$$ farthest from $$u$$ (either by rooting the tree in $$u$$ or using BFS).
The algorithm you describe is also correct, because a middle vertex of the tree is also a vertex $$v$$ such that the tree rooted in $$v$$ has minimal height $$h$$. Removing leaves means reducing the height by one (and the root is necessarily removed last, because the tree has two children of height $$h-1$$ and $$h-1-\varepsilon$$, with $$\varepsilon\in \{0,1\}$$, otherwise using another root would reduce its height).