##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 233.05123

**Autor: ** Chvatal, V.; Erdös, Paul

**Title: ** A note on Hamiltonian circuits. (In English)

**Source: ** Discrete Math. 2, 111-113 (1972).

**Review: ** 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 [*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 223.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).

**Classif.: ** * 05C45 Eulerian and Hamiltonian graphs

05C38 Paths and cycles

05C40 Connectivity

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag