How to Use an Obstruction Test
A Hamiltonicity obstruction certificate is a verifiable reason that a graph cannot have a Hamiltonian cycle. Some certificates are local, such as a vertex of degree one; others identify a vertex set whose removal leaves too many components. A failed necessary condition rules out Hamiltonicity. Passing one, or even several, such tests does not establish that a Hamiltonian cycle exists.
Throughout, graphs are finite and simple. A Hamiltonian cycle is a cycle containing every vertex of the graph. A graph is Hamiltonian if it has such a cycle. For a vertex set \(S\subseteq V(G)\), \(G-S\) is the subgraph induced by \(V(G)\setminus S\), and \(c(G-S)\) is its number of connected components; by convention, the graph with no vertices has zero components. An independent set is a set of vertices no two of which are adjacent. A graph is bipartite if its vertices can be partitioned into two sets so every edge joins different sets.
The tests below are necessary conditions: a Hamiltonian graph must pass them. Their purpose is to find a certificate when it does not. If all tests considered pass, the conclusion is only that those tests have not provided a certificate.
Necessary Conditions and Their Certificates
- Every vertex has degree at least \(2\), and \(G\) has no cut vertex.
- For each nonempty \(S\subseteq V(G)\), \(c(G-S)\leq |S|\).
- Every independent set \(I\) satisfies \(|I|\leq n/2\).
- If \(G\) is bipartite with parts \(X,Y\), then \(|X|=|Y|\).
Proof. Let \(C\) be a Hamiltonian cycle. Each vertex has two distinct neighbors along \(C\), so its degree in \(G\) is at least \(2\). Deleting any one vertex from \(C\) leaves a path through all other vertices. Thus deleting one vertex from \(G\) leaves a connected graph, so no vertex is a cut vertex.
Now let \(S\) be nonempty. Removing \(|S|\) vertices from a cycle leaves at most \(|S|\) nonempty path segments: each segment, if any remain, begins immediately after a removed vertex as one goes around the cycle. The graph \(G-S\) contains all the edges of these remaining segments and may contain additional edges, which can join segments but cannot create more components. Hence \(c(G-S)\leq |S|\).
For an independent set \(I\), each vertex of \(I\) has two incident edges on \(C\), and those edges go to vertices outside \(I\). There are therefore \(2|I|\) cycle edges from \(I\) to \(V(G)\setminus I\). Each vertex outside \(I\) is incident with at most two edges of \(C\), so \(2|I|\leq 2(n-|I|)\). Dividing by \(2\) gives \(|I|\leq n/2\).
Finally, if \(G\) is bipartite, every edge of \(C\) alternates between \(X\) and \(Y\). Traversing the cycle therefore visits the same number of vertices from each part. Since \(C\) contains every vertex, \(|X|=|Y|\). \(\square\)
Each failed condition can be stated as a concise certificate: a vertex of degree less than \(2\), a cut vertex, a set \(S\) with \(c(G-S)>|S|\), an independent set larger than \(n/2\), or unequal bipartition sizes. The component-count condition includes the cut-vertex test: if deleting one vertex leaves at least two components, then \(c(G-S)>1=|S|\).
Toughness packages component-count certificates into a ratio. The component-count theorem proves the required inequality directly; no separate assumption about connectivity after deleting several vertices is needed. In the examples, a single set with ratio below \(1\) is enough to show the graph fails the necessary toughness bound.
Worked Examples: Two Complete Bipartite Graphs
Worked Example: The Star \(K_{1,3}\)
Let \(G=K_{1,3}\), with \(V(G)=\{x,a,b,c\}\) and \(E(G)=\{xa,xb,xc\}\). Its bipartition is \(X=\{x\}\), \(Y=\{a,b,c\}\). We apply the tests one by one.
The degrees are \(\deg(x)=3\) and \(\deg(a)=\deg(b)=\deg(c)=1\). Since \(1<2\), any leaf is a degree certificate. Also, deleting \(x\) leaves three isolated vertices, so \(c(G-\{x\})=3>1=|\{x\}|\). The same set gives a toughness ratio \(1/3\), since \(|\{x\}|/c(G-\{x\})=1/3<1\).
The bipartition is unbalanced: \(|X|=1\) and \(|Y|=3\), with \(1\ne3\). The set \(I=\{a,b,c\}\) is independent, and \(|I|=3>4/2=2\). Each is an obstruction certificate. The graph also has a cut vertex, namely \(x\).
Check: A Hamiltonian cycle would require two cycle edges at each leaf, but each leaf has only one incident edge. This directly confirms the degree certificate; it is consistent with the other failed necessary conditions.
Worked Example: The Graph \(K_{2,3}\)
Let \(G=K_{2,3}\), with \(V(G)=\{u,v,a,b,c\}\), \(X=\{u,v\}\), \(Y=\{a,b,c\}\), and \(E(G)=\{ua,ub,uc,va,vb,vc\}\). There are no edges within either part.
The degrees are \(\deg(u)=\deg(v)=3\) and \(\deg(a)=\deg(b)=\deg(c)=2\). Thus the minimum degree is \(2\), so the degree test does not rule out Hamiltonicity. The graph has no cut vertex: deleting \(u\) leaves the star with center \(v\) and leaves \(a,b,c\); deleting \(a\) leaves \(K_{2,2}\), which is connected. The same forms apply when deleting any vertex in the corresponding part. So the cut-vertex test also does not rule it out.
However, take \(S=\{u,v\}\). The remaining graph has vertices \(a,b,c\) and no edges, so \(c(G-S)=3>2=|S|\). This is a component-count certificate. Its toughness ratio is \(|S|/c(G-S)=2/3<1\). The bipartition sizes are \(2\) and \(3\), which are unequal, and \(I=\{a,b,c\}\) is an independent set of size \(3>5/2\). Thus the bipartition and independent-set tests also rule out a Hamiltonian cycle.
Check: A Hamiltonian cycle in a bipartite graph must alternate between its parts and use equally many vertices of each part. Here those sizes are \(2\) and \(3\), so such a cycle cannot include all five vertices. This verifies the bipartition certificate independently of the component count.
The contrast between these examples is useful. For \(K_{1,3}\), the degree test already gives an immediate certificate. For \(K_{2,3}\), every vertex has enough degree and no single vertex disconnects the graph, yet larger-set tests detect the obstruction. A test that passes is not a guarantee: it merely means that particular necessary condition has not supplied a contradiction.
Worked Example: What the Tests Say About the Petersen Graph
Worked Example: The Petersen Graph
Define the Petersen graph \(P\) with vertices \(V(P)=\{a_i,b_i: i\in\{0,1,2,3,4\}\}\), where indices are taken modulo \(5\), and edges \(E(P)=\{a_i a_{i+1}:0\leq i\leq4\}\cup\{a_i b_i:0\leq i\leq4\}\cup\{b_i b_{i+2}:0\leq i\leq4\}\). The first set forms an outer 5-cycle, the second consists of spokes, and the third forms the inner 5-cycle in star order. Each vertex has two neighbors in its cycle and one spoke neighbor, so every degree is \(3\). The degree test passes.
The earlier result that the Petersen graph is hypohamiltonian means that it is not Hamiltonian, but deleting any one vertex leaves a Hamiltonian graph. In particular, deleting any one vertex leaves a connected graph, so the Petersen graph has no cut vertex. This test passes too.
In fact its component-count test passes for every vertex set. To verify this, let \(S\) be nonempty. If \(|S|=1\), hypohamiltonicity says \(P-S\) is Hamiltonian and therefore connected, so \(c(P-S)=1=|S|\). If \(|S|\geq2\), choose \(x\in S\). The graph \(P-x\) has a Hamiltonian cycle. Deleting the other \(|S|-1\) vertices from that cycle leaves at most \(|S|-1\) path segments. The graph \(P-S\) may have extra edges between those segments, but cannot have more components than the segments. Hence \(c(P-S)\leq |S|-1<|S|\). In particular, \(P\) satisfies the necessary toughness bound \(t(P)\geq1\).
For the independent-set test, take \(I=\{a_0,a_2,b_3,b_4\}\). None of the chosen pairs is an edge: \(a_0\) and \(a_2\) are not consecutive on the outer cycle, \(b_3\) and \(b_4\) are not adjacent in the inner star, and none of the chosen \(a\)-vertices has its spoke endpoint among the chosen \(b\)-vertices. Thus \(I\) is independent and \(|I|=4\leq 10/2=5\), so it does not obstruct Hamiltonicity.
Moreover, \(\alpha(P)=4\), where \(\alpha(P)\) is the maximum size of an independent set. To see the upper bound, suppose \(P\) had an independent set \(J\) of size at least \(5\), and choose five of its vertices. Since \(P\) is 3-regular, the chosen five vertices have \(5\cdot3=15\) incident edges, all going to the other five vertices. The other five vertices have total degree \(5\cdot3=15\), so all their incident edges go to the chosen set; there can be no edges within either set. This would make \(P\) bipartite. But the outer edges include the 5-cycle \(a_0a_1a_2a_3a_4a_0\), which is odd and cannot alternate between two parts. This contradiction proves \(\alpha(P)\leq4\). The displayed independent set gives equality.
The bipartition-balance test is not applicable to \(P\), because \(P\) is not bipartite: its outer 5-cycle cannot alternate between two parts. This is not a Hamiltonicity certificate. It says only that this particular necessary condition for a bipartite graph cannot be used here.
Check: The Petersen graph has \(10\) vertices, and its independent-set bound is \(\alpha(P)\leq10/2=5\). The computed value \(4\) satisfies that bound. Its degree, cut, component-count, toughness and independent-set tests therefore provide no obstruction; the bipartition test does not apply. The tests considered here do not explain why the graph is non-Hamiltonian, even though the earlier hypohamiltonicity result establishes that fact.
Reading the Results Carefully
A certificate is decisive because it contradicts a condition every Hamiltonian graph must satisfy. The validity of the certificate does not depend on having found every possible obstruction. In particular, a single set \(S\) with \(c(G-S)>|S|\) is enough; there is no need to calculate the graph's exact toughness.
The reverse inference is invalid. Minimum degree at least \(2\), absence of cut vertices, balanced bipartition when applicable, and the independent-set bound do not together guarantee a Hamiltonian cycle. The Petersen example makes this distinction concrete: several necessary conditions hold, but the graph is still not Hamiltonian. These tests are most useful as a disciplined first pass: state the condition, exhibit the violating vertex or set if one exists, and otherwise record that the test was inconclusive.
A common mistake is to treat “passes the test” as a positive Hamiltonicity criterion. For \(K_{2,3}\), the minimum-degree calculation gives \(\delta(G)=2\), and deleting any single vertex leaves the graph connected. Those are correct calculations, but they do not prove the existence of a Hamiltonian cycle. The correction is to test larger sets: \(S=\{u,v\}\) gives \(c(G-S)=3>2=|S|\), which decisively rules one out.
Check Your Understanding
For each question, distinguish a certificate from a test that merely passes or does not apply.
- In \(K_{1,3}\), identify a degree certificate and a component-count certificate.
- Why does minimum degree \(2\) not settle Hamiltonicity for \(K_{2,3}\)? Give a set that does provide a certificate.
- Prove that if a graph has an independent set \(I\) with \(|I|>|V(G)|/2\), then it cannot be Hamiltonian.
- What does the bipartition-balance test say about a graph containing an odd cycle? Explain why this is not, by itself, a Hamiltonicity obstruction.
- For the Petersen graph, why does passing the component-count test not contradict its non-Hamiltonicity?