complexity of finding the hampath of length $k$ in a graph with $n$ vertexes where $k < n$
Purely for clarity I'll lay out the definitions first, then give a reduction for your problem, so skipping a little ahead shouldn't cause a problem (if it does, start a bit earlier ;) ).
The two problems:

Hamiltonian Path (HP)
Input: A graph $G$.
Question: Does $G$ contain a path with $|V(G)|$ vertices?
Not Quite Longest Path (NQLP)
Input: A graph $G$ and an integer $k &lt; |V(G)|$.
Question: Does $G$ contain a path on $k$ vertices?

Now, what we want to prove:

Lemma 1: NQLP is $\mathcal{NP}$-complete.

Of course this has two parts, membership and hardness.

Proposition 2: NQLP $\in \mathcal{NP}$

Proof: Given an order set of vertices we can easily check that it is of length $k$ and forms a path in $G$. $\Box$

Proposition 3: HP $\leq_{m}$ NQLP

Proof: Let $G$ be an instance of HP and for convenience let $n = |V(G)|$. We construct an instance $(G', k)$ of NQLP by taking $G'$ as $G$ with an additional, disconnected vertex $v$, i.e. $V(G') = V(G)\cup \{v\}$ and $E(G') = E(G)$. Thus $|V(G')| = n' = n+1$. We choose $k = n &lt; n'$. This construction is clearly computable in polynomial time.
Claim: If $G$ has a Hamiltonian path, $G'$ has a path of length $k$.
By definition, the Hamilton path includes all vertices of $G$, as $G'$ has $G$ as an (induced) subgraph, this path exists in $G'$. Moreover it is of length $n = k$.
Claim: If $G'$ has a path of length $k$, $G$ is has a Hamiltonian path.
If $G'$ contains a path of length $k$, it cannot include the added vertex $v$, as it has no incident edges (except the trivial case where $G$ was one vertex, but then we have a symmetry which does our work for us). Therefore it must include every other vertex in $G'$ (as $k = n' -1 = n$), as $G' - v$ is simply $G$, $G$ must be Hamiltonian. $\Box$
Proof of Lemma 1: As HP is $\mathcal{NP}$-complete, Prop. 3 proves that NQLP is $\mathcal{NP}$-hard. Then combining Propositions 2 &amp; 3, we have proved Lemma 1. $\Box$