Sufficient Conditions Are Not Characterizations

Sufficient Does Not Mean Necessary

A condition can be a reliable way to prove that a graph has a Hamiltonian cycle without being required for every Hamiltonian graph. This distinction matters when using a criterion: if its hypothesis fails, that tells us the test has not certified Hamiltonicity; it does not show that a Hamiltonian cycle is absent. We will compare four familiar sufficient conditions with explicit graphs that have Hamiltonian cycles but fail those conditions.

A Hamiltonian cycle in a finite simple graph \(G=(V,E)\) is a cycle that visits every vertex exactly once before returning to its starting vertex. A graph containing such a cycle is Hamiltonian. A displayed cycle proves Hamiltonicity directly, regardless of whether a degree or connectivity test applies.

Definition: A condition \(P\) is sufficient for Hamiltonicity if every graph satisfying \(P\) is Hamiltonian. It is necessary if every Hamiltonian graph satisfies \(P\). A condition is a characterization when it is both necessary and sufficient.

For example, if \(P\) is sufficient, the implication is \(P\Rightarrow\text{Hamiltonian}\). To show that \(P\) is not necessary, it is enough to exhibit a Hamiltonian graph for which \(P\) is false. That example disproves the reverse implication; it does not disprove the sufficiency theorem.

Four Sufficient Conditions

Here are the four standard results in the form needed for comparison. The Hamiltonian-cycle material establishes these as sufficient criteria; their proofs are not needed to test whether their hypotheses are necessary.

Theorem (Dirac’s theorem): If \(G\) is a simple graph of order \(n\ge3\) and \(\delta(G)\ge n/2\), then \(G\) is Hamiltonian.

Theorem (Ore’s theorem): If \(G\) is a simple graph of order \(n\ge3\) and \(\deg(u)+\deg(v)\ge n\) for every pair of distinct nonadjacent vertices \(u,v\), then \(G\) is Hamiltonian.

For the degree-sequence condition, write the degrees in nondecreasing order as \(d_1\le d_2\le\cdots\le d_n\), counting each vertex once.

Theorem (Chvatal’s condition): If \(G\) is a simple graph of order \(n\ge3\) and, for every integer \(k\) with \(1\le k<n/2\), \(d_k\le k\) implies \(d_{n-k}\ge n-k\), then \(G\) is Hamiltonian.

The final criterion uses the vertex connectivity \(\kappa(G)\), the minimum number of vertices whose deletion disconnects a connected, noncomplete graph, and the independence number \(\alpha(G)\), the largest size of a set of pairwise nonadjacent vertices.

Theorem (Chvatal–Erdos condition): If \(G\) is a simple graph of order \(n\ge3\) and \(\kappa(G)\ge\alpha(G)\), then \(G\) is Hamiltonian. For a complete graph, the usual convention is \(\kappa(K_n)=n-1\); complete graphs of order at least three are Hamiltonian directly.

These conditions test different graph data: minimum degree, degree sums across nonedges, the ordered degree sequence, and the comparison between connectivity and independence. The examples below show why failure of any one of these hypotheses is not itself a certificate of non-Hamiltonicity.

A Cycle That Fails All Four Tests

Worked Example: The Six-Cycle

Let \(G\) have vertex set \(V=\{1,2,3,4,5,6\}\) and edge set \(E=\{12,23,34,45,56,61\}\). The cycle \(1,2,3,4,5,6,1\) uses all six vertices exactly once, so \(G\) is Hamiltonian.

Each vertex has degree \(2\), since each is incident with its two cycle edges. Thus \(\delta(G)=2\), while \(n/2=6/2=3\). Since \(2<3\), Dirac’s hypothesis fails. Vertices \(1\) and \(3\) are nonadjacent, and \(\deg(1)+\deg(3)=2+2=4<6=n\), so Ore’s hypothesis fails as well.

The ordered degree sequence is \(d_1=d_2=d_3=d_4=d_5=d_6=2\). For \(k=2\), we have \(1\le2<6/2=3\), and \(d_2=2\le2\). Chvatal’s condition would then require \(d_{6-2}=d_4\ge6-2=4\). But \(d_4=2<4\), so this condition fails.

To check Chvatal–Erdos, the set \(\{1,3,5\}\) is independent, so \(\alpha(G)\ge3\). No independent set can contain more than three vertices: the three disjoint edges \(12,34,56\) allow at most one endpoint of each in an independent set. Hence \(\alpha(G)=3\).

Deleting one vertex from the cycle leaves a path through the other five vertices, so one vertex cannot disconnect \(G\). Deleting vertices \(2\) and \(5\) leaves two components, with vertex sets \(\{1,6\}\) and \(\{3,4\}\). Therefore \(\kappa(G)=2\), and \(\kappa(G)=2<3=\alpha(G)\). The Chvatal–Erdos hypothesis fails too.

Check: The displayed cycle proves Hamiltonicity, while the calculations give \(2<3\) for Dirac, \(4<6\) for Ore, \(d_4=2<4\) in Chvatal’s condition, and \(2<3\) for Chvatal–Erdos. Thus this one graph violates all four hypotheses and remains Hamiltonian.

The Conditions Can Behave Differently

A single counterexample for each condition is enough to show that it is not necessary. Comparing examples also helps prevent a different mistake: treating the four conditions as interchangeable. In particular, a graph may pass one test while failing another.

Worked Example: The Five-Cycle Passes Chvatal–Erdos

Let \(H\) have vertex set \(V(H)=\{1,2,3,4,5\}\) and edge set \(E(H)=\{12,23,34,45,51\}\). The cycle \(1,2,3,4,5,1\) is Hamiltonian. Every vertex has degree \(2\), so \(\delta(H)=2<5/2\); Dirac’s condition fails. The nonadjacent vertices \(1\) and \(3\) have degree sum \(2+2=4<5\), so Ore’s condition fails.

For Chvatal’s condition, the sorted degrees are all \(2\). At \(k=2\), we have \(1\le2<5/2\) and \(d_2=2\le2\). The condition would require \(d_{5-2}=d_3\ge5-2=3\), but \(d_3=2<3\). Thus Chvatal’s condition fails.

The largest independent set in \(H\) has size \(2\). For an upper bound, each selected vertex in an independent set must be followed around the cycle by an unselected vertex; these followers are distinct, so an independent set has at most \(\lfloor5/2\rfloor=2\) vertices. The set \(\{1,3\}\) is independent, so \(\alpha(H)=2\).

Deleting any one vertex leaves a path on the other four vertices, which is connected. Deleting vertices \(1\) and \(3\) leaves vertices \(2,4,5\), with \(4\) adjacent to \(5\) and \(2\) isolated. Hence \(\kappa(H)=2\), and \(\kappa(H)=\alpha(H)=2\).

Check: This graph fails Dirac, Ore, and Chvatal’s hypotheses, but satisfies the Chvatal–Erdos comparison exactly. Its displayed Hamiltonian cycle confirms that passing or failing one criterion should not be confused with the outcome of another test.

Worked Example: Adding a Chord Does Not Repair the Degree Tests

Let \(J\) have vertex set \(V(J)=\{1,2,3,4,5,6\}\) and edge set \(E(J)=\{12,23,34,45,56,61,14\}\). The six-cycle \(1,2,3,4,5,6,1\) is still present, so \(J\) is Hamiltonian; the extra edge \(14\) is a chord.

Vertices \(1\) and \(4\) each have degree \(3\), and vertices \(2,3,5,6\) each have degree \(2\). Therefore \(\delta(J)=2<6/2=3\), so Dirac’s condition fails. Vertices \(2\) and \(5\) are nonadjacent and have degree sum \(2+2=4<6\), so Ore’s condition fails.

The degree sequence is \(2,2,2,2,3,3\). At \(k=2\), \(d_2=2\le2\), which would require \(d_4\ge6-2=4\). But \(d_4=2<4\), so Chvatal’s condition fails.

The set \(\{1,3,5\}\) is independent: none of the three pairs \(13,15,35\) is an edge of \(J\). Thus \(\alpha(J)\ge3\). Deleting vertices \(1\) and \(4\) leaves precisely the edges \(23\) and \(56\), so the remaining graph is disconnected. On the other hand, deleting any one vertex leaves the other five connected through the six-cycle with that vertex removed. Hence \(\kappa(J)=2\), and \(\kappa(J)=2<3\le\alpha(J)\). The Chvatal–Erdos condition fails.

Check: The cycle is an explicit Hamiltonian cycle in \(J\), and the chord changes some degrees without making any of the four stated hypotheses true. The example confirms that the relevant check must be made on the actual graph, not inferred from the presence of an extra edge.

What the Counterexamples Establish

Proposition. If a Hamiltonian graph fails a stated sufficient condition, that condition is not necessary for Hamiltonicity.

Proof. Let \(P\) be the condition and let \(H\) be Hamiltonian with \(P\) false. If \(P\) were necessary, every Hamiltonian graph would satisfy \(P\), so \(H\) would satisfy \(P\). This contradicts the choice of \(H\). Therefore \(P\) is not necessary. \(\square\)

Applying the proposition to the six-cycle shows that none of Dirac’s, Ore’s, Chvatal’s, or Chvatal–Erdos’s hypotheses is necessary. The conclusion is limited but useful: these theorems provide sufficient certificates. When a graph fails a test, the appropriate next step is to use other information, such as an explicit cycle or a different method—not to conclude that the graph is non-Hamiltonian.

There is also a common logical pitfall here. From “if the degree condition holds, then the graph is Hamiltonian,” one cannot infer “if the degree condition fails, then the graph is not Hamiltonian.” That would reverse the implication. The six-cycle is a concrete correction: its minimum degree is \(2<3\), but the sequence \(1,2,3,4,5,6,1\) is a Hamiltonian cycle. Likewise, its failed Ore, Chvatal, and Chvatal–Erdos checks do not erase that cycle.

Check Your Understanding

For each question, separate what a criterion guarantees from what its failure tells you.

For the graph \(C_6\) in the first example, identify the exact value of \(k\) that violates Chvatal’s condition and state the required inequality.
Why does one nonadjacent pair with degree sum less than \(n\) suffice to show that Ore’s hypothesis fails?
In the five-cycle example, which of the four conditions is satisfied, and what are the values of \(\kappa(H)\) and \(\alpha(H)\)?
Explain why \(\delta(G)<n/2\) does not prove that \(G\) is non-Hamiltonian.
Give the logical form of a sufficient condition for Hamiltonicity, and state what kind of example disproves its necessity.