Show that if $G$ is a $k$-connected graph with at least 3 vertices such that any $k+1$ vertices of $G$ span at least one edge, then the graph is hamiltonian.
I know that a graph is said to be $k$-connected if there does not exist a set of $k-1$ vertices whose removal disconnects the graph. Also, a graph is hamiltonian if it contains a hamiltonian cycle, which is a cycle that visits every vertex exactly once.
This problem has been getting to me for the past two days and I would really appreciate some assistance in solving this. It comes from the book Modern Graph Theory by Bela Bollobas.
Many thanks in advance for your time and suggestions.