Three Tests Every Hamiltonian Graph Must Pass
A Hamiltonian cycle visits every vertex of a graph exactly once before returning to its starting vertex. Its structure imposes immediate restrictions on the graph: the cycle itself connects all vertices, and each vertex uses two incident edges of the cycle. Also, removing one vertex from the cycle leaves a path through all the other vertices. These observations give useful tests for ruling out Hamiltonicity.
Throughout, graphs are finite and simple. The order of \(G\) is \(n=|V(G)|\), and the minimum degree is \(\delta(G)=\min\{\deg(v):v\in V(G)\}\). A graph is connected if every pair of its vertices is joined by a path. A Hamiltonian cycle is a cycle containing every vertex of the graph; a graph containing one is called Hamiltonian. We consider Hamiltonian graphs of order \(n\ge3\), so a cycle has at least three vertices.
The three conditions are necessary, not sufficient: a Hamiltonian graph of order at least three is connected, has minimum degree at least two, and has no cut vertex. In particular, if any one of these conditions fails, the graph cannot be Hamiltonian. We prove each condition before using it.
Why the Conditions Are Necessary
Proof. Let \(C\) be a Hamiltonian cycle of \(G\). First, any two vertices of \(G\) can be joined by following one of the routes along \(C\) between them. Thus \(G\) is connected.
Next, fix any vertex \(v\). In the cycle \(C\), the vertex \(v\) has a predecessor and a successor. Because \(C\) has length at least three and its vertices are distinct before returning to the start, these are two distinct vertices. The two cycle edges incident with \(v\) are therefore distinct edges of \(G\), so \(\deg(v)\ge2\). This holds for every vertex \(v\), which gives \(\delta(G)\ge2\).
Finally, suppose that \(v\) were a cut vertex. Write the Hamiltonian cycle in order as \(v,v_1,v_2,\ldots,v_{n-1},v\). Deleting \(v\) from this cycle leaves the path \(v_1,v_2,\ldots,v_{n-1}\). Every vertex of \(G-v\) appears on this path, so \(G-v\) is connected: between any two of its vertices, a segment of the path gives a path in \(G-v\). This contradicts the assumption that \(v\) is a cut vertex. Hence \(G\) has no cut vertex. \(\square\)
The argument also indicates what the tests measure. Connectivity is forced by the cycle as a whole; the degree bound comes from the two cycle edges at each vertex; and the cut-vertex condition follows because removing one cycle vertex leaves a spanning path on all the others. None of these arguments says that a graph with the three properties must contain a Hamiltonian cycle.
Using Connectivity and Degree
Worked Example: Two Separate Triangles
Let \(G\) have vertex set \(V(G)=\{1,2,3,4,5,6\}\) and edge set \(E(G)=\{12,23,31,45,56,64\}\). Each of the vertex sets \(\{1,2,3\}\) and \(\{4,5,6\}\) induces a triangle, and there are no edges between them.
The neighbors of \(1,2,3\) are, respectively, \(\{2,3\},\{1,3\},\{1,2\}\), so each has degree \(2\). The neighbors of \(4,5,6\) are \(\{5,6\},\{4,6\},\{4,5\}\), so each also has degree \(2\). Thus \(\delta(G)=2\). But a vertex in \(\{1,2,3\}\) has no path to a vertex in \(\{4,5,6\}\), so \(G\) is disconnected and cannot be Hamiltonian.
Check: The graph has \(3+3=6\) edges and degree sum \(6\cdot2=12=2\cdot6\), consistent with the fact that each edge contributes one to the degree of each endpoint. The degree test passes, but the connectivity test fails.
Worked Example: A Cycle with a Pendant Vertex
Let \(G\) have \(V(G)=\{1,2,3,4,5\}\) and \(E(G)=\{12,23,34,41,15\}\). The edges \(12,23,34,41\) form a 4-cycle, and vertex \(5\) is attached to vertex \(1\) by edge \(15\).
From the edge list, the neighborhoods are \(N(1)=\{2,4,5\}\), \(N(2)=\{1,3\}\), \(N(3)=\{2,4\}\), \(N(4)=\{1,3\}\), and \(N(5)=\{1\}\). The degrees are therefore \(3,2,2,2,1\), giving \(\delta(G)=1\). The graph is connected: vertices \(2,3,4,5\) are all joined to \(1\) by paths. Nevertheless, it cannot have a Hamiltonian cycle, since vertex \(5\) has only one incident edge, while every vertex on a cycle has two distinct incident cycle edges.
Check: The degrees sum to \(3+2+2+2+1=10\), and the five listed edges give \(2|E(G)|=2\cdot5=10\). The computation confirms that the pendant vertex, not a failure of connectivity, is what rules out Hamiltonicity.
Using the Cut-Vertex Condition
Worked Example: Two Triangles Sharing a Vertex
Let \(G\) have \(V(G)=\{1,2,3,4,5\}\) and \(E(G)=\{12,23,31,14,45,51\}\). The triangles \(1,2,3,1\) and \(1,4,5,1\) share vertex \(1\), but no other vertices or edges.
The neighbors of \(1\) are \(\{2,3,4,5\}\), so \(\deg(1)=4\). Each of \(2,3,4,5\) has two neighbors: \(2\) is adjacent to \(1,3\); \(3\) to \(1,2\); \(4\) to \(1,5\); and \(5\) to \(1,4\). Hence the degree list is \(4,2,2,2,2\), and \(\delta(G)=2\). The graph is connected because each vertex is adjacent to \(1\) or joined to \(1\) by one edge.
Now delete vertex \(1\). The remaining graph has vertex set \(\{2,3,4,5\}\) and edges \(\{23,45\}\). Its two components have vertex sets \(\{2,3\}\) and \(\{4,5\}\); there is no path between them. Thus \(1\) is a cut vertex, so the theorem rules out a Hamiltonian cycle.
Check: The six listed edges give \(2|E(G)|=2\cdot6=12\), and the degree sum is \(4+2+2+2+2=12\). The graph passes the minimum-degree test but fails the cut-vertex test.
The deletion test is applied to a connected graph: a cut vertex is defined here as a vertex whose deletion disconnects that graph. For a Hamiltonian graph, the theorem says that deleting any single vertex must leave a connected graph. Finding just one vertex whose deletion disconnects \(G\) is enough to reject Hamiltonicity.
Worked Example: Passing the Tests Is Not Enough
Let \(G\) have \(V(G)=\{a,b,x,y,z\}\) and \(E(G)=\{ab,ax,bx,ay,by,az,bz\}\). Every one of \(x,y,z\) is adjacent to both \(a\) and \(b\), and \(a\) and \(b\) are adjacent.
The degrees are \(\deg(a)=4\), from neighbors \(b,x,y,z\); \(\deg(b)=4\), from neighbors \(a,x,y,z\); and \(\deg(x)=\deg(y)=\deg(z)=2\), since each is adjacent to \(a,b\). Therefore \(\delta(G)=2\). The graph is connected because every vertex is either \(a\) or adjacent to \(a\).
It has no cut vertex. Deleting \(a\) leaves the edges \(bx,by,bz\), so the remaining graph is connected through \(b\). Deleting \(b\) leaves the edges \(ax,ay,az\), so the remaining graph is connected through \(a\). If one of \(x,y,z\) is deleted, the edge \(ab\) remains and each of the two other vertices among \(x,y,z\) remains adjacent to both \(a\) and \(b\). The resulting graph is connected in each case.
Despite passing all three necessary tests, \(G\) is not Hamiltonian. In any Hamiltonian cycle, each of \(x,y,z\) would have to use both of its incident edges, since it has only those two edges available. This would force the cycle to use \(ax,ay,az\), giving vertex \(a\) at least three incident edges in the cycle. But a cycle has exactly two incident cycle edges at each of its vertices. This contradiction proves that no Hamiltonian cycle exists.
Check: There are seven listed edges, and the degree sum is \(4+4+2+2+2=14=2\cdot7\). Thus the degree calculation agrees with the edge count, while the forced-edge argument independently establishes non-Hamiltonicity.
Common Pitfalls and Practical Use
Do not treat a necessary condition as sufficient. A tempting but incorrect calculation for the graph of two triangles sharing vertex \(1\) is: “Every degree is at least \(2\), so the graph is Hamiltonian.” The degree calculation is correct—its minimum degree is \(2\)—but the conclusion is not. Deleting \(1\) leaves two components, so \(1\) is a cut vertex and the graph cannot be Hamiltonian. The degree condition is a test that every Hamiltonian graph must pass, not a criterion that proves a cycle exists.
Check the definition of a cut vertex using deletion. A vertex is not a cut vertex merely because it has high degree, low degree, or lies on several cycles. The relevant question is whether \(G-v\) is disconnected. Conversely, failure of the minimum-degree condition and failure of the cut-vertex condition are different obstructions: the pendant-vertex graph fails the degree test, while the two-triangle graph fails the cut-vertex test.
These tests are most useful as quick rejection tools. For a proposed Hamiltonian graph of order at least three, first check whether it is connected, then whether every degree is at least \(2\), and, for each candidate vertex, whether deleting it leaves a connected graph. If any check fails, Hamiltonicity is impossible. If all checks pass, a Hamiltonian cycle has not yet been established; the last worked example demonstrates why further reasoning is needed.
Check Your Understanding
For each question, justify your answer using the definitions and necessary conditions proved above.
- Why does a Hamiltonian cycle force the whole graph to be connected?
- Explain why the condition \(n\ge3\) ensures that a vertex on a Hamiltonian cycle has two distinct cycle neighbors.
- Let \(G\) have \(V(G)=\{1,2,3,4\}\) and \(E(G)=\{12,23,31,14\}\). Which necessary condition rules out Hamiltonicity?
- In the graph with edges \(ab,ax,bx,ay,by,az,bz\), explain why degree \(2\) at \(x,y,z\) forces too many cycle edges at \(a\).
- Why does passing the connectivity, minimum-degree, and no-cut-vertex tests not by itself prove that a graph is Hamiltonian?