Condition for Complete Bipartite Graph to be Semi-Hamiltonian

Theorem

Let $K_{m, n}$ be a complete bipartite graph.

Then $K_{m, n}$ is semi-Hamiltonian iff either:

• $m = n = 1$;

• $m = n + 1$ (or $n = m + 1$).

Proof

Let $K_{m, n}$ be a complete bipartite graph.

• If $m = n = 1$ then $K_{m, n} = K_{1, 1}$ is trivially semi-Hamiltonian:

• If $m = n + 1$, we can construct a Hamiltonian path as follows.

Let $K_{m, n} = \left({A \mid B, E}\right)$ such that $|A| = m, A = \left\{{u_1, u_2, \ldots, u_m}\right\}, |B| = n, B = \left\{{v_1, v_2, \ldots, v_m}\right\}$.

We start at vertex $u_1 \in A$.

As $K_{m, n}$ is complete, there is an edge connecting $u_1$ to $v_1$.

From $v_1$, there is an edge connecting $v_1$ to $u_2$.

And so on.

There is therefore a Hamiltonian path $\left({u_1, v_1, u_2, v_2, \ldots, u_{n-1}, v_{n-1}, u_n, v_n, u_m}\right)$ (where of course $u_m = u_{n+1}$).

So when $m = n + 1$, $K_{m, n}$ has a Hamiltonian path.

However, from Condition for Bipartite Graph to be Hamiltonian, $K_{m, n}$ is only fully Hamiltonian if $m = n$.

Hence when $m = n + 1$, $K_{m, n}$ is semi-Hamiltonian.

Similarly, if $n = m + 1$ the same argument applies, but this time the Hamiltonian path is $\left({v_1, u_1, v_2, y_2, \ldots, v_{n-1}, y_{n-1}, v_m, u_m, v_n}\right)$ (where of course $v_n = u_{m+1}$).

• Now, suppose $K_{m, n}$ is such that neither $m = n + 1$ nor $n = m + 1$, and it is not the case that $m = n = 1$.

If $m = n$, then from Condition for Bipartite Graph to be Hamiltonian $K_{m, n}$ is Hamiltonian, and therefore not semi-Hamiltonian.

If $m > n+1$, then we can once more trace a path through $K_{m, n} = \left({A \mid B, E}\right)$ as before, but at the end of the path there is a spare vertex in $A$ which has not been traversed which you can't get to without going back to one of the vertices in $B$ that you have already visited.

Similarly if $n > n+1$.

Hence the result.

$\blacksquare$