Is this an NP-Complete problem? (unweighted & undirected graph)

Question

G is an unweighted, undirected graph. Then, I cannot prove that [deciding whether G has a path of length greater than k] is NP-Complete.

How can I show whether the algorithm is NP-complete or not?

Answer 1

Let $G$ be your graph, and let it have $n$ vertices.

The Hamiltonian path problem is NP-complete. $G$ has a Hamiltionian path if and only if its longest path has length $n - 1$. Thus, the decision problem you described must be NP-complete.

Answer 2

This problem can be shown to NP-hard by reducing the longest path problem to it. It's not hard to do so maybe you want to give it a try first before I give you the reduction.