In the
mathematical field of
graph theory, a complete bipartite graph or biclique is a special kind of
bipartite graph where every
vertex of the first set is connected to every vertex of the second set.[1][2]
A complete bipartite graph is a graph whose vertices can be partitioned into two subsets V1 and V2 such that no edge has both endpoints in the same subset, and every possible edge that could connect vertices in different subsets is part of the graph. That is, it is a
bipartite graph(V1, V2, E) such that for every two vertices v1 ∈ V1 andv2 ∈ V2, v1v2 is an edge in E. A complete bipartite graph with partitions of size |V1| = m and |V2| = n, is denoted Km,n;[1][2] every two graphs with the same notation are
isomorphic.
Examples
The
star graphsK1,3, K1,4, K1,5, and K1,6.A complete bipartite graph of K4,7 showing that
Turán's brick factory problem with 4 storage sites (yellow spots) and 7 kilns (blue spots) requires 18 crossings (red dots)
For any k, K1,k is called a
star.[2] All complete bipartite graphs which are
trees are stars.
The graph K3,3 is called the
utility graph. This usage comes from a standard mathematical puzzle in which three utilities must each be connected to three buildings; it is impossible to solve without crossings due to the
nonplanarity of K3,3.[6]
The maximal bicliques found as subgraphs of the digraph of a relation are called concepts. When a lattice is formed by taking meets and joins of these subgraphs, the relation has an
Induced concept lattice. This type of analysis of relations is called
formal concept analysis.
Regular complex polygons of the form 2{4}p have complete bipartite graphs with 2p vertices (red and blue) and p2 2-edges. They also can also be drawn as p edge-colorings.
Given a bipartite graph, testing whether it contains a complete bipartite subgraph Ki,i for a parameter i is an
NP-complete problem.[8]
Every complete bipartite graph. Kn,n is a
Moore graph and a (n,4)-
cage.[10]
The complete bipartite graphs Kn,n and Kn,n+1 have the maximum possible number of edges among all
triangle-free graphs with the same number of vertices; this is
Mantel's theorem. Mantel's result was generalized to k-partite graphs and graphs that avoid larger
cliques as subgraphs in
Turán's theorem, and these two complete bipartite graphs are examples of
Turán graphs, the extremal graphs for this more general problem.[11]
Every complete bipartite graph is a
modular graph: every triple of vertices has a median that belongs to shortest paths between each pair of vertices.[15]
See also
Biclique-free graph, a class of sparse graphs defined by avoidance of complete bipartite subgraphs