A survey on the Chvátal-Erdös theorem

In 1857, the Irish mathematician Sir William Hamilton(1805-1865) invented a game of travelling around the edges of a graph from vertex to vertex. Hamilton described the game, in a letter to his friend Graves, as a mathematical game on the dodecahedron in which one person sticks five pins in any five consecutive vertices and the other is required to complete the path to form a spanning cycle. In other words, given a particular graph to begin with, the objective of the game was to find a path in the graph which passes through each vertex exactly once. Such a graph is called a Hamiltonian graph. For a long time there was no elegant characterization of Hamiltonian graphs, although several necessary and sufficient conditions were known. Interested readers may consult graph theory books by Bondy and Murty[3], Harary [10] and Diestel [7] for relevant materials. First, let us present a useful necessary condition: Theorem 1.1. If G is hamiltonian then, for every nonempty proper subset S of V, we have ω(G − S) � |S|. Proof. Let C be a hamiltonian cycle in G. Then, for every nonempty proper subset S of V, we have ω(C −S) � |S|. Since C −S is a spanning subgraph of G −S, ω(G −S) � ω(C −S). Therefore, ω(G − S) � ω(C − S) � |S|. Note 1.2. Since a graph is hamiltonian if and only if its underlying simple graph is hamiltonian, it suffices to limit our discussion to simple graphs. Example 1.3 (Illustration of theorem 1.1). Consider a graph with nine vertices; on deleting the three in black, four components remain. Therefore, the condition of theorem 1.1 is not satisfied and it follows that the graph is nonhamiltonian. We can see that the theorem 1.1 can sometimes be used to show that a particular graph is nonhamiltonian. However, this method does not always work; for instance, the Petersen graph is nonhamiltonian, but one cannot deduce this by using theorem 1.1. The following theorems provide sufficient conditions for a graph being Hamiltonian: