Let $G$ be an undirected graph. A vertex cover of $G$ is a subset of vertices where every edge of $G$ touches one of the vertices. The problem $\text{VERTEX-COVER}$ is: Given a graph $G$ and an integer $k$, does $G$ contain a vertex cover of size $k$?
Theorem. $\text{VERTEX-COVER}$ is $\mathbf{NP}$-complete.
Proof. To see that $\text{VERTEX-COVER}$ is in $\mathbf{NP}$, we note that a suitable certificate is the vertex cover of size $k$. Now, we show that $\text{CLIQUE} \leq_P \text{VERTEX-COVER}$.
Given a graph $G = (V,E)$, we want to know whether or not it has a clique of size $k$. We consider the graph $\overline G = (V,\overline E)$, where $\overline E$ is the set of edges not in $G$. In other words, if there was no edge between $u$ and $v$ in $G$, $(u,v)$ is an edge in $\overline G$. Conversely, if $(u,v)$ is an edge in $G$, then it is not an edge in $\overline G$. We claim that $G$ has a clique of size $k$ if and only if $\overline G$ has a vertex cover of size $|V| - k$.
First, suppose that $G$ contains a clique $C$ of size $k$. Then let $(u,v)$ be an edge in $\overline G$, so $(u,v)$ is not an edge in $G$. This means that either $u$ or $v$ is not in $C$, since if they were both in $C$, then $(u,v)$ would need to be in $G$. Then either $u$ or $v$ is in $V \setminus C$. Thus, each edge in $\overline G$ has at least one endpoint in $V \setminus C$, which makes $V \setminus C$ a vertex cover for $\overline G$ of size $|V| - k$.
Now, we suppose that $\overline G$ has a vertex cover $C'$ of size $|V| - k$. Then for any edge $(u,v)$ of $\overline G$, either $u$ or $v$ is in $C'$. Now if both $u$ and $v$ are not in $C'$, then $(u,v)$ is not an edge in $\overline G$. That is, if both $u$ and $v$ are not in $V \setminus C'$, then $(u,v)$ is an edge in $G$. That means that $V \setminus C'$ is a clique of size $|V| - (|V| - k) = k$ in $G$. $$\tag*{$\Box$}$$
A linear program is is a set of linear inequalities with rational coefficients over variables $x_1, \dots, x_n$. A linear program is an integer program if there is an assignment of integers to $x_1,\dots,x_n$ that satisfies it.
Theorem. $\mathrm{IP}$ is $\mathbf{NP}$-complete.
Proof. It is not difficult to see that $\mathrm{IP}$ is in $\mathbf{NP}$. We will show $\mathbf{NP}$-completeness by a reduction from $\text{VERTEX-COVER}$. To do this, we have to formulate the vertex cover problem as an integer program. To do this, given a graph $G = (V,E)$, we'll define a variable $x_v$ for each vertex $v \in V$ by $$ x_v = \begin{cases} 1 & v \in C, \\ 0 & v \not\in C, \end{cases}$$ where $C$ is a vertex cover. Then we add the following constraints:
$$\tag*{$\Box$}$$
It turns out that while integer programming is $\mathbf{NP}$-complete, the original problem of linear programming (where solutions are not restricted to the integers) is solvable in polynomial time. Furthermore, we can surmise from the reduction we just worked through that restricting the solution space for integer programming doesn't make the problem any easier: our reduction only used values of 0 and 1. In other words, the problem of 0-1 integer programming is also $\mathbf{NP}$-complete.
We showed that $\mathrm{HAMPATH}$ was in $\mathbf{NP}$ earlier. Now, we'll show that it is in fact $\mathbf{NP}$-complete.
Theorem. $\mathrm{HAMPATH}$ is $\mathbf{NP}$-complete.
Proof. We've already shown that this is in NP. So, we just need to show that this is NP-complete by reducing from $\mathrm{3SAT}$.
To do this, we construct a graph $G$ based on a 3CNF formula $\varphi$. The graph $G$ has the following vertices:
In addition to the edges in each chain, we add edges from $v_{start}$ to $v_1$ and $v_{6m}$ of the first chain. Similarly, we add edges from $v_1$ and $v_{6m}$ of the $n$th chain to $v_{end}$. For the chains in between, we add edges from $v_1$ and $v_{6m}$ to both $v_1$ and $v_{6m}$ of the $j+1$st chain.
Finally, for each clause $C$ of $\varphi$, we add edges for the variables appearing in $C$. If $C$ contains a literal $u_j$, then we add an edge from $v_i$ to $v_C$ and $v_C$ to $v_{i+1}$ in the $j$th chain. However, if $C$ contains $\overline u_j$, then we add the edge from $v_{i+1}$ to $v_C$ and from $v_C$ to $v_i$, again in the $j$th chain.
When doing this, we do not want to reuse any links and we want to keep a link between two used links. We ensure we have enough links to do this by making each chain have $6m$ vertices.
Now, we suppose that $\varphi$ has a satisfying assignment $u_1, \dots, u_n$. We need to show that there's a path that visits all vertices. We start at $v_{start}$, go through each chain, and end at $v_{end}$. First, we note that if $u_j$ is True, we traverse the chain from left to right and if $u_j$ is False, we traverse the chain from right to left. To deal with the clause vertices, we note that if $u$ is a satisfying assignment, then for every clause $C$, there's at least one literal that is linked to the corresponding vertex $v_C$ that is true, and we can modify the path along one of the chains which reaches $v_C$ easily so that it visits $v_C$ as well.
Next, we suppose $G$ has a Hamitonian path $P$. By our construction, $P$ must start at $v_{start}$ since it has no incoming edges and end at $v_{end}$ since it has no outgoing edges. We also need to traverse each chain in order and we need to traverse each chain completely either going from left to right or right to left. To visit a clause vertex, the path must return to the same chain, otherwise, there will either be unreachable vertices or it will reach a chain that has already been traversed. Now, we have the assignment $u_1, \dots, u_n$ for $\varphi$ where $u_j$ is True if $P$ traverses chain $j$ from left to right and $u_j$ is False if $P$ traverses chain $j$ from right to left. Since $P$ visits every vertex, we have a satisfying assignment. $$\tag*{$\Box$}$$