The diameter of a graph is the largest of all shortest-path distances in it. How can we find a tree of maximum diameter within an undirected unweighted graph?
Note that the tree does not have to be a spanning tree.
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
This (probably) can't be done efficiently since a maximum-diameter spanning tree could be a Hamiltonian path.
More specifically, an $n$-vertex graph has a tree of diameter $n-1$ as a subgraph if, and only if, it has a Hamiltonian path (the tree is the Hamiltonian path). Therefore, the problem of finding a maximum-diameter subtree is NP-hard, since you can reduce Hamiltonian path to it by finding the maximum-diameter subtree and checking whether or not it's a path of length $n-1$.