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.

  • $\begingroup$ what does to "spat" an edge mean? do you mean span? $\endgroup$ – Siddharth Bhat May 4 '16 at 18:22
  • $\begingroup$ Thanks for the observation, I have included the edit. $\endgroup$ – Jamil_V May 4 '16 at 18:41
  • $\begingroup$ First observe what is a Hamiltonian; A graph G on n ≥ 3 vertices $\endgroup$ – D.d.C May 4 '16 at 19:46
  • $\begingroup$ κ(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. $\endgroup$ – D.d.C May 4 '16 at 19:57
  • $\begingroup$ "with at least 3 vertices span at least one-edge" what does that mean? $\endgroup$ – Ofek Ron Aug 16 '16 at 17:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.