How to find tree in a graph with maximal possible height?

Question

You should assume that regular graph is given. Graph is not multigraph and has no self-edges. I am looking for algo with upper bound of O(n^2)

Answer 1

The tree with maximal height will include (from root to leaf) the longest possible path in G.

The problem of finding the longest path in an unweighted, undirected graph is NP-hard. By consequence there is no O(n²) algorithm to solve it.