Chapter 6, Problem 67E

Complete bipartite graphs. A complete bipartite graph is a graph with the property that the vertices can be divided into two sets A and B and each vertex in a set $A$ is adjacent to each of the vertices in set $B$. There are no other edges! If there are m vertices in set A and n vertices in set B, the complete bipartite graph is written as $K_{m,n}$. $Figure6-52$ shows a generic bipartite graph.

$Figure6-52$

a. For $n>1$, the complete bipartite graphs of the form $K_{n,n}$ all have Hamilton circuits. Explain why.

b. If the difference between m and n is exactly 1 $\left(\text{i}\text{.e}\text{., }|m-n|=1\right),$ the complete bipartite graph $K_{m,n}$ has Hamilton path. Explain why.

c. When the difference between m and n is more than 1, then the complete bipartite graph $K_{m,n}$ has neither a Hamilton circuit nor a Hamilton path. Explain why.