A note on Hamiltonian circuits (Q2551113): Difference between revisions

The purpose of this note is to prove the following Theorem 1. Let \(G\) be a graph with at least three vertices. If, for some \(s\), \(G\) is \(s\)-connected and contains no independent set of more than \(s\) vertices, then \(G\) has a Hamiltonian circuit. This theorem is sharp. For \(s\) relatively large with respect to the number of vertices of \(G\), our Theorem 1 follows from a stronger statement due to Nash-Williams and Bondy [\textit{C. St. J. A. Nash-Williams}, Studies pure Math., Papers presented to Richard Rado on the Occasion of his sixty-fifth Birthday, 157-183 (1971; Zbl 0223.05123), Lemma 4]. As an easy consequence of Theorem 1 we obtain Theorem 2. Let \(G\) be an \(s\)-connected graph with no independent set of \(s+2\) vertices. Then \(G\) has a Hamiltonian path. The technique used in the proof of Theorem 1 yields also Theorem 3. Let \(G\) be an \(s\)-connected graph containing no independnet set of \(s\) vertices. Then \(G\) is Hamiltonian-connected (i.e. every pair of vertices is joined by a Hamiltonian path).