LONG-PATH is the problem of, given (G, u, v, k) where G is a graph, u and v vertices and k an integer, determining if there is a simple path in G from u to v of length at least k.
Show that LONG-PATH is NP-complete.
Consider the following given data of the problem LONG-PATH (G, u, v, k):
G = G is a graph.
u, v = are vertices of the graph.