# Finding a maximum-diameter tree in an undirected unweighted graph

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.

• It makes no difference whether the tree is spanning or not. If there is a tree of diameter $d$, there is a spanning tree of diameter $d$ or greater so the question "Is there a tree of diameter $d$?" has the same complexity as "Is there a spanning tree of diameter $d$?" – David Richerby Nov 6 '14 at 12:46

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$.
• @Bangye Careful. $\Sigma^*$ includes Hamiltonian path, too. – Raphael Nov 6 '14 at 12:58