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 the two sets have 
and 
graph vertices, where 
and 
are positive integers, the complete bipartite
graph is denoted 
. The above figures show 
and 
.
is also known as the utility graph (and is the circulant graph 
), and is the unique 4-cage
graph. 
is a Cayley graph. A complete bipartite graph 
is a circulant graph (Skiena 1990, p. 99),
specifically 
,
where 
is the floor function.
Special cases of 
are summarized in the table below.
The graphs 
and 
are outer-cylindrical forbidden
minors No. 1 and 
(No. 31), respectively (Archdeacon et al. 2001).
is Hamiltonian iff 
and 
.
For 
,
has no Hamiltonian cycles. For 
, 3, ..., their numbers are 1, 6, 72, 1440, 43200, 1814400,
101606400, ... (OEIS A010796), given by 
,
where 
is a factorial. 
is traceable iff 
,
since any Hamiltonian path must alternate between
the two bipartition classes.
Complete bipartite graphs are graceful.
Zarankiewicz's conjecture posits a closed form for the graph crossing number of 
.
The Klein bottle crossing number of 
is 
,
where 
is the floor function (Richter and Širáň
1996). Koman (1975) proved further exact cases. For 
, the values for 
are 0, 2, 4, 6, and 8, respectively, while the values
for 
,
,
and 
are 5, 8, and 12, respectively.
For a positive integer 
, the independence polynomial
of 
is given by
 |
(1)
|
which satisfies the recurrence relation for 
 |
(2)
|
The matching polynomial is given by
 |
(3)
|
where 
is a Laguerre polynomial, and the matching-generating
polynomial by
 |
(4)
|
with the value at 
defined by continuity.
has a true Hamilton decomposition iff 
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).
on the Klein Bottle." In Recent Advances in
Graph Theory. Prague, Czechoslovakia: Academia, pp. 327-334, 1975.Laskar,
R. and Auerbach, B. "On Decomposition of 
-Partite Graphs into Edge-Disjoint Hamilton Circuits."
Disc. Math. 14, 265-268, 1976.Richter, R. B. and
Širáň, J. "The Crossing Number of 
in a Surface." J. Graph Th. 21, 51-54,
1996.