Alternation Determines the Answer
A complete bipartite graph has two vertex classes, with every possible edge between the classes and no edges within either class. This structure makes Hamiltonian questions especially concrete: along any path or cycle, consecutive vertices must come from opposite classes. Since a Hamiltonian path or cycle visits every vertex, the way the classes can alternate places an exact restriction on their sizes.
All graphs here are finite and simple. For integers \(m,n\ge 0\), let \(K_{m,n}\) have disjoint vertex classes \(A\) and \(B\), where \(|A|=m\) and \(|B|=n\), and edge set consisting of every pair \(ab\) with \(a\in A\) and \(b\in B\). There are no other edges. A path is a sequence of distinct vertices in which consecutive vertices are adjacent; its length is the number of consecutive pairs. A cycle in a simple graph is a cyclic sequence of at least three distinct vertices, with consecutive vertices—including the last and first—adjacent.
The single-vertex convention matters for \(K_{0,1}\) and \(K_{1,0}\): each consists of one vertex and no edges, so each has a Hamiltonian path of length zero. For the cycle result, the minimum length requirement rules out any graph on fewer than three vertices.
Hamiltonian Paths
Proof. First suppose \(K_{m,n}\) has a Hamiltonian path. Its vertices appear in a sequence, and each consecutive pair must lie in opposite classes because there are no edges within \(A\) or within \(B\). Thus the sequence alternates between \(A\) and \(B\). In an alternating sequence, the numbers of terms from the two classes are equal if the sequence has even length, and differ by one if it has odd length. To verify this, group consecutive terms into pairs, each containing one term from each class; if the sequence has odd length, exactly one unpaired term remains, at one end. Since the sequence contains all \(m+n\) vertices, this gives \(|m-n|\le 1\).
Conversely, suppose \(m+n\ge1\) and \(|m-n|\le1\). If \(m=n=k\ge1\), list the vertices as \(a_1,b_1,a_2,b_2,\dots,a_k,b_k\), where the \(a_i\) are the vertices of \(A\) and the \(b_i\) are the vertices of \(B\). Every consecutive pair has one endpoint in each class, so every consecutive pair is an edge of \(K_{m,n}\). The list is therefore a path containing every vertex. If \(m=n+1\), list them as \(a_1,b_1,\dots,a_n,b_n,a_{n+1}\); if \(n=0\), this list is simply \(a_1\). Again, consecutive vertices are in opposite classes, and the list contains all vertices. The case \(n=m+1\) is obtained by starting with a vertex of \(B\) and alternating in the same way. These cases include every nonempty pair of sizes with difference at most one, so the condition is sufficient. \(\square\)
The proof gives a construction, not just a test: alternate the classes, placing an extra vertex from the larger class at one end when the sizes differ by one. When the sizes differ by more than one, alternation cannot use every vertex, because the smaller class cannot separate all the vertices of the larger class.
Worked Example: A Hamiltonian Path in \(K_{4,3}\)
Let \(A=\{a_1,a_2,a_3,a_4\}\) and \(B=\{b_1,b_2,b_3\}\). Define \(G=K_{4,3}\) with vertex set \(A\cup B\) and edge set \(E=\{a_1b_1,a_1b_2,a_1b_3,a_2b_1,a_2b_2,a_2b_3,a_3b_1,a_3b_2,a_3b_3,a_4b_1,a_4b_2,a_4b_3\}\). Since \(4-3=1\), the theorem predicts a Hamiltonian path.
Start with a vertex from the larger class and alternate: \(a_1,b_1,a_2,b_2,a_3,b_3,a_4\). The consecutive pairs are \(a_1b_1\), \(b_1a_2\), \(a_2b_2\), \(b_2a_3\), \(a_3b_3\), and \(b_3a_4\). Each appears in the edge set, and the list contains all seven vertices exactly once. It is a Hamiltonian path.
Check: the path has six edges, as a path on seven distinct vertices must: there is one edge between each consecutive pair, hence \(7-1=6\). The displayed sequence has exactly six consecutive pairs. The class sizes differ by one, agreeing with the necessary condition.
Worked Example: No Hamiltonian Path in \(K_{4,2}\)
Let \(A=\{a_1,a_2,a_3,a_4\}\), \(B=\{b_1,b_2\}\), and define \(G=K_{4,2}\) with vertex set \(A\cup B\) and edge set \(E=\{a_1b_1,a_1b_2,a_2b_1,a_2b_2,a_3b_1,a_3b_2,a_4b_1,a_4b_2\}\). Here \(|4-2|=2\), so the theorem says there is no Hamiltonian path.
To see the obstruction directly, a path alternating between the classes can place at most one more \(A\)-vertex than \(B\)-vertices: with two \(B\)-vertices, the longest alternating sequence that starts and ends in \(A\) has the form \(A,B,A,B,A\), containing only three \(A\)-vertices. A Hamiltonian path would need to include four \(A\)-vertices as well as both \(B\)-vertices. The required alternating sequence cannot exist.
Check: the graph has eight edges because each of the four vertices of \(A\) is adjacent to both vertices of \(B\), giving \(4\cdot2=8\); the listed edge set has eight pairs. The presence of many edges does not fix the position-count obstruction: a path cannot use two consecutive vertices of \(A\).
Hamiltonian Cycles
Proof. Suppose \(K_{m,n}\) has a Hamiltonian cycle. Read its vertices in cyclic order. Each step must switch classes, including the step from the final vertex back to the first. Therefore the classes alternate all the way around the cycle. Every time the cyclic order leaves a vertex of \(A\), it next visits a vertex of \(B\), and the alternating order returns to \(A\); consequently the cycle contains equally many vertices of each class. Since it is Hamiltonian, this means \(m=n\). A cycle in a simple graph has at least three vertices. An alternating cyclic sequence has even length, so its length is at least four; hence the common class size is at least two.
For the converse, suppose \(m=n=k\ge2\). Write the vertices in the order \(a_1,b_1,a_2,b_2,\dots,a_k,b_k\), and then return from \(b_k\) to \(a_1\). Every consecutive pair, including \(b_k a_1\), has one endpoint in each class and is an edge. The \(2k\) listed vertices are distinct, so this is a cycle; its length is \(2k\ge4\), and it contains every vertex. Thus it is Hamiltonian. \(\square\)
The two requirements in this theorem have different roles. Equality of the class sizes is forced by alternation around a closed sequence. The lower bound \(m=n\ge2\) ensures that the resulting cycle has at least four distinct vertices. Equal class sizes alone do not guarantee a cycle when both sizes are one.
Worked Example: A Hamiltonian Cycle in \(K_{3,3}\)
Let \(A=\{a_1,a_2,a_3\}\), \(B=\{b_1,b_2,b_3\}\), and define \(G=K_{3,3}\) with vertex set \(A\cup B\) and edge set \(E=\{a_1b_1,a_1b_2,a_1b_3,a_2b_1,a_2b_2,a_2b_3,a_3b_1,a_3b_2,a_3b_3\}\). The class sizes are equal and at least two. The alternating cyclic order \(a_1,b_1,a_2,b_2,a_3,b_3,a_1\) uses the edges \(a_1b_1,a_2b_1,a_2b_2,a_3b_2,a_3b_3,a_1b_3\), so it is a Hamiltonian cycle.
Check: the cycle uses six distinct vertices and six edges, with the last edge \(b_3a_1\) closing the sequence. The complete graph \(K_{3,3}\) has \(3\cdot3=9\) edges, matching the nine pairs in the displayed edge set. The cycle uses six of these nine edges, as expected; a Hamiltonian cycle need not use every edge.
Comparing the Two Conditions
A Hamiltonian path has two ends, so an alternating path can have one more vertex from one class than the other. A Hamiltonian cycle has no ends: alternation must also hold across the closing edge, forcing exact equality. This explains why the path condition allows class sizes to differ by one, whereas the cycle condition does not.
| Question for \(K_{m,n}\) | Exact condition | Reason from alternation |
|---|---|---|
| Hamiltonian path | \(m+n\ge1\) and \(|m-n|\le1\) | A linear alternating sequence has equal class counts or a difference of one. |
| Hamiltonian cycle | \(m=n\ge2\) | A cyclic alternating sequence has equal counts and at least four vertices. |
These conditions are specific to complete bipartite graphs. Alternation gives necessary restrictions in any bipartite graph, but satisfying the class-size condition alone does not create the required edges in an arbitrary bipartite graph. Here sufficiency works because every vertex in one class is adjacent to every vertex in the other, so each constructed alternating sequence is guaranteed to use edges.
Common Pitfall: Counting the Alternating Positions Incorrectly
A tempting but incorrect claim is that a path can have arbitrarily many vertices from one class by placing them in a row and using the other class whenever needed. A path cannot place two vertices from the same class consecutively: there is no edge between them. For instance, with two vertices in \(B\), an alternating path can have at most three vertices in \(A\), in the pattern \(A,B,A,B,A\). It cannot contain four \(A\)-vertices, as the \(K_{4,2}\) example shows.
Another mistake is to apply the path condition to cycles and conclude that class sizes may differ by one. A path can start and end in the larger class, accounting for the extra vertex. In a cycle, the last vertex must also be adjacent to the first, so the alternation closes only when the class counts are equal. In particular, \(K_{3,2}\) has a Hamiltonian path but no Hamiltonian cycle.
For quick decisions, first identify whether the question asks for a path or a cycle, then compare the sizes of the two classes. For paths, check that the graph is nonempty and the difference is at most one. For cycles, check both equality and that each class has at least two vertices. The constructions in the proofs then provide a witness whenever the condition holds.
Check Your Understanding
Use alternation to justify each answer, and give an explicit vertex order whenever a path or cycle exists.
- Does \(K_{5,4}\) have a Hamiltonian path? Does it have a Hamiltonian cycle?
- Does \(K_{2,2}\) have a Hamiltonian path and a Hamiltonian cycle? Write a sequence for each.
- Why does \(K_{1,1}\) have a Hamiltonian path but no Hamiltonian cycle?
- What is the largest possible number of vertices from one class in an alternating path that uses exactly three vertices from the other class?
- Explain why the class-size conditions alone would not guarantee a Hamiltonian path in every bipartite graph.