Alternation Forces Balance
A Hamiltonian cycle must visit every vertex, so any restriction on how cycles pass through a graph can rule out Hamiltonicity. In a bipartite graph, every step along a cycle switches from one vertex class to the other. Returning to the starting vertex therefore requires the cycle to use the two classes equally often. This simple counting obstruction is especially useful when the classes have different sizes.
All graphs in this tutorial are finite and simple. A cycle is a closed sequence of at least three edges whose vertices are distinct except for the repeated starting vertex at the end. A cycle is Hamiltonian if it contains every vertex of the graph. A graph is Hamiltonian if it has a Hamiltonian cycle; in particular, a Hamiltonian graph has at least three vertices.
For a cycle in a bipartite graph, the vertices alternate between the classes. The key point is that this applies to the entire cycle, not merely to a path along part of it. Closing the cycle forces the alternation to return to its initial class in exactly the right parity.
The Balance Theorem
Proof. Let the cycle have length \(\ell\), and write its vertices in order as \(v_0,v_1,\ldots,v_{\ell-1}\), with the final edge \(v_{\ell-1}v_0\). Every edge joins different classes. Thus, starting from \(v_0\), the cycle alternates between \(X\) and \(Y\). Since the cycle returns to \(v_0\), its length must be even: after an odd number of switches, the walk would be in the class opposite to that of \(v_0\). Write \(\ell=2k\). Of the \(2k\) vertices in the cycle, the vertices in even positions \(v_0,v_2,\ldots,v_{2k-2}\) are in the same class as \(v_0\), and the \(k\) vertices in odd positions \(v_1,v_3,\ldots,v_{2k-1}\) are in the other class. Therefore the cycle uses exactly \(k\) vertices from each class. If it is Hamiltonian, it uses every vertex, so \(|X|=|Y|=k\). \(\square\)
The theorem gives a necessary condition, not a complete test. If the two classes have different sizes, there cannot be a Hamiltonian cycle. If they have equal sizes, the theorem does not promise that a Hamiltonian cycle exists: the arrangement of the edges still matters.
Proof. A Hamiltonian cycle uses all \(n\) vertices. By the theorem it uses the same number of vertices from each class, say \(k\) from each. Thus \(n=k+k=2k\), so \(n\) is even and both classes have size \(k=n/2\). \(\square\)
Worked Examples
Worked Example: The Complete Bipartite Graph \(K_{2,3}\)
Let \(G=K_{2,3}\) have vertex set \(V=\{a,b,1,2,3\}\) and edge set \(E=\{a1,a2,a3,b1,b2,b3\}\). Its bipartition is \(X=\{a,b\}\) and \(Y=\{1,2,3\}\). Decide whether \(G\) is Hamiltonian.
The class sizes are \(|X|=2\) and \(|Y|=3\). If \(G\) had a Hamiltonian cycle, that cycle would use all five vertices. The balance theorem would then require \(2=3\), which is false. Therefore \(G\) is not Hamiltonian.
Check: A Hamiltonian cycle would have length \(5\), since it would include all five vertices. But a cycle in a bipartite graph has even length, as each edge switches classes and returning to the starting class requires an even number of switches. The odd length \(5\) is another direct contradiction.
Worked Example: A Balanced Bipartite Graph That Is Hamiltonian
Let \(G\) have vertex set \(V=\{1,2,3,4\}\), edge set \(E=\{13,14,23,24\}\), and bipartition \(X=\{1,2\}\), \(Y=\{3,4\}\). Find and check a Hamiltonian cycle.
The class sizes are \(|X|=2\) and \(|Y|=2\), so the balance obstruction does not rule out a Hamiltonian cycle. The sequence \(1,3,2,4,1\) is a cycle: its successive edges are \(13,32,24,41\), all of which are in \(E\). The vertices \(1,3,2,4\) are distinct, and together they include all of \(V\), so this is a Hamiltonian cycle.
Check: The cycle uses the two vertices \(1,2\) from \(X\) and the two vertices \(3,4\) from \(Y\), as required. It also uses four distinct edges from the displayed edge set and returns to its starting vertex.
Worked Example: Balance Is Not Sufficient
Let \(G\) have vertex set \(V=\{1,2,3,4\}\), edge set \(E=\{12,23,34\}\), and bipartition \(X=\{1,3\}\), \(Y=\{2,4\}\). The classes have equal size. Determine whether \(G\) is Hamiltonian.
The balance theorem gives no obstruction because \(|X|=|Y|=2\). However, vertex \(1\) is incident with just one edge, namely \(12\). In any cycle, each vertex on the cycle must be incident with two distinct edges of that cycle: one by which the cycle enters the vertex and one by which it leaves. A Hamiltonian cycle would include vertex \(1\), but \(1\) has only one incident edge in \(G\). Thus \(G\) is not Hamiltonian.
Check: The graph is a path \(1,2,3,4\). Its only possible route through all four vertices in sequence uses edges \(12,23,34\), and this route does not return from \(4\) to \(1\), since \(41\notin E\). Equal class sizes are therefore necessary for Hamiltonicity in a bipartite graph, but they are not sufficient.
Using the Obstruction Carefully
The balance test is an efficient one-way certificate. To use it, first give a valid bipartition \(X,Y\), then compare the class sizes. If they differ, the theorem rules out Hamiltonicity immediately. If they agree, the test is inconclusive and another argument is needed. It is not valid to reverse the theorem and claim that every balanced bipartite graph is Hamiltonian.
When a graph is presented by an edge list, a proposed bipartition must be checked against every edge: each listed edge must have one endpoint in each part. After that, count the vertices in the parts, not the edges. The obstruction concerns how many vertices a cycle must use from each class.
| What the check finds | Conclusion | Reason |
|---|---|---|
| The graph is bipartite and \(|X|\ne|Y|\) | Not Hamiltonian | A Hamiltonian cycle would use equally many vertices from the two classes. |
| The graph is bipartite and \(|X|=|Y|\) | No conclusion from balance alone | Other features of the edges may still prevent a Hamiltonian cycle. |
| A proposed partition has an edge within one part | The proposed partition is invalid | Every edge must cross between the two parts. |
Common Pitfall
Wrong calculation: For the graph in the third example, one might observe that \(|X|=2\) and \(|Y|=2\), then conclude that the graph is Hamiltonian. This incorrectly treats a necessary condition as sufficient. Correction: equal class sizes merely allow the balance condition to hold. Check whether the graph actually contains a cycle through every vertex; here vertex \(1\) has degree \(1\), so it cannot lie on any cycle, and the graph is not Hamiltonian.
A different mistake is to count the edges in each direction of an alternating cycle as though they could compensate for unequal vertex counts. They cannot: each move changes classes, and the cycle must return to its starting vertex. The theorem counts the vertices visited in each class, which must match exactly.
Why This Condition Matters
Hamiltonicity can be difficult to establish by searching through possible cycles. A counting obstruction can settle some cases before any search begins. For a bipartite graph, comparing the two class sizes is especially quick: it uses only the partition and a vertex count. The examples also show the proper role of such a test. A mismatch proves non-Hamiltonicity; a match says only that this particular obstruction has not ruled it out.
Check Your Understanding
For each question, state the relevant partition or cycle condition and justify the conclusion.
- A bipartite graph has classes of sizes \(4\) and \(5\). Can it have a Hamiltonian cycle? Why?
- Let \(V=\{a,b,c,d,e,f\}\) and \(E=\{ad,ae,af,bd,be,bf,cd,ce,cf\}\). Give a bipartition and use the balance condition to decide whether the graph can be Hamiltonian.
- Give an example of a bipartite graph with equal-sized classes that is not Hamiltonian, and explain the obstruction.
- Prove directly from alternation that every cycle in a bipartite graph has even length.
- Why does equal class size not prove that a bipartite graph is Hamiltonian?