Complete bipartite graphs. A complete bipartite graph isa graph with the property th...

Complete bipartite graphs. A complete bipartite graph isa graph with the property that the vertices can be dividedinto two sets A and B and each vertex in set A is adjacentto each of the vertices in set B. There are no other edges! Ifthere are m vertices in set A and n vertices in set B, the complete bipartite graph is written as Km, n. Figure 6-56 shows ageneric bipartite graph.

(a) For n > 1, the complete bipartite graphs of the formK_{m, n} all have Hamilton circuits. Explain why.

(b) If the difference between m and n is exactly 1 (i.e.,|m – n| = 1), the complete bipartite graph K_{m, n} has aHamilton 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 aHamilton circuit nor a Hamilton path. Explain why.