Prove that a graph is Hamiltonian Prove that if a graph $G$ is $k$-connected and $\alpha(G) \le k$ then $G$ is Hamiltonian.
Where $\alpha(G) $ is the size of the largest independent set in $G.$
 A: This is:

Chvátal-Erdős Theorem: Let $G$ be a $k$-connected graph with $n \geq 3$ vertices.  If $\alpha(G)\leq k$ then $G$ is Hamiltonian.

It was proved in:

Chvátal V., Erdős P., A note on Hamiltonian circuits, Discrete Math. 2 (1972),
  111-113.  (pdf)

Here's a sketch of the proof.  (Note: the result is only true when $G$ has $n \geq 3$ vertices.)
Step 1:  If $k=1$, then $G=K_n$, which is Hamiltonian since $n \geq 3$.  Now assume $k \geq 2$.  
Step 2:  Let $C$ be the largest cycle in $G$.  If $C$ is not Hamiltonian, then there is a vertex $x$ outside of $C$.  Since $G$ is $k$-connected, there are $k$ paths from $C$ to $x$ which are disjoint apart from $x$; call the terminal vertices $x_1,x_2,\ldots,x_k$.
If two of the $x_i$'s are next to each other, we can find a longer cycle as depicted below:

Since this cycle is longer than $C$, we have a contradiction.
Step 3: For each $x_i$, define its successor $y_i$ to be the vertex adjacent to $x_i$ when we go around $C$ in some fixed direction.  Importantly, we can assume $\{y_i\}_{i=1}^k \cap \{x_i\}_{i=1}^k = \emptyset$ (otherwise, we're at a situation covered by Step 2).
Since $\alpha(G) \leq k$, there exists a pair of vertices in $\{y_i\}_{i=1}^k$ that are adjacent (otherwise $\{y_i\}_{i=1}^k \cup \{x\}$ is an independent set of size $k+1$).
Hence we can find a longer cycle as depicted below:

Since this cycle is longer than $C$, we have a contradiction.
