I conisder a problem:
It is given a graph $G$, vertices $s,t$, $k$- length of the graph. Prove that decision whether there is a path between $s$ and $t$ of length $k$ is NP-complete.
Please note that in our problem we have a path, not a **simple path* **
*It is trivial when we have a simple path (define as sequence of vertices where every vertice occurs at most once (there is no cycle) ).
I don't know how to start. I cannot come up what's problem I should reduce. Please hint me.