A complete bipartite graph, sometimes also called a complete bicolored graph (Erdős et al. 1965) or complete bigraph, is a bipartite
graph (i.e., a set of graph vertices decomposed
into two disjoint sets such that no two graph vertices
within the same set are adjacent) such that every pair of graph
vertices in the two sets are adjacent. If there are and graph vertices in the two
sets, the complete bipartite graph is denoted . The above figures show and .

The numbers of (directed) Hamiltonian cycles for the graph
with ,
2, ... are 0, 2, 12, 144, 2880, 86400, 3628800, 203212800, ... (OEIS A143248),
where the th
term for
is given by
with
a factorial.

has a true Hamilton decompositioniff
and
is even, and a quasi-Hamilton decomposition iff and is odd (Laskar and Auerbach 1976; Bosák 1990, p. 124).

The complete bipartite graph illustrated above plays an important role in the novel
Foucault's
Pendulum by Umberto Eco (1989, p. 473; Skiena 1990, p. 143).

Bosák, J. Decompositions of Graphs. New York: Springer, 1990.Chia, G. L. and Sim,
K. A. "On the Skewness of the Join of Graphs." Disc. Appl. Math.161,
2405-2409, 2013.Eco, U. Foucault's
Pendulum. San Diego: Harcourt Brace Jovanovich, p. 473, 1989.Erdős,
P.; Harary, F.; and Tutte, W. T. "On the Dimension of a Graph." Mathematika12,
118-122, 1965.Laskar, R. and Auerbach, B. "On Decomposition of
-Partite
Graphs into Edge-Disjoint Hamilton Circuits." Disc. Math.14,
265-268, 1976.Saaty, T. L. and Kainen, P. C. The
Four-Color Problem: Assaults and Conquest. New York: Dover, p. 12, 1986.Skiena,
S. Implementing
Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading,
MA: Addison-Wesley, 1990.Sloane, N. J. A. Sequence A143248
in "The On-Line Encyclopedia of Integer Sequences."