# Show that if any $k+1$ vertices of $k-$connected graph with at least 3 vertices span at least one-edge, then the graph is hamiltonian.

Show that if any $k+1$ vertices of $k-$connected graph with at least 3 vertices span at least one-edge, then the graph is hamiltonian.

I know that a graph $G$ 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 is coming from the book Modern Graph Theory by Bella Ballobas.

Many thanks in advance for your time and suggestions.

• what does to "spat" an edge mean? do you mean span? – Siddharth Bhat May 4 '16 at 18:22
• Thanks for the observation, I have included the edit. – Jamil_V May 4 '16 at 18:41
• First observe what is a Hamiltonian; A graph G on n ≥ 3 vertices – D.d.C May 4 '16 at 19:46
• κ(G) A connected graph G is k-connected if |V (G)| ≥ k+1 and G−S is connected for any set S ⊂ V (G) of at most k−1 vertices. In other words, no two vertices are separated by a set of k − 1 vertices. – D.d.C May 4 '16 at 19:57
• "with at least 3 vertices span at least one-edge" what does that mean? – Ofek Ron Aug 16 '16 at 17:35