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. Graph theory itself is typically dated as beginning with Leonhard Euler's 1736 work on the Seven Bridges of Königsberg. However, drawings of complete bipartite graphs were already printed as early as 1669, in connection with an edition of the works of Ramon Llull edited by Athanasius Kircher. Llull himself had made similar drawings of complete graphs three centuries earlier.

Definition

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 and v2 ∈ V2 , v1v2 is an edge in E. A complete bipartite graph with partitions of size = m and = n , is denoted Km,n

Examples

Star graphs.svg K1,3 , K1,4 , K1,5 , and K1,6 .]] [[File:Zarankiewicz K4 7.svg|thumb|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)]] K1,k is called a star. All complete bipartite graphs which are trees are stars. K1,3 is called a claw, and is used to define the claw-free graphs. 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 .

Properties

Ki,i for a parameter i is an NP-complete problem. K3,3 as a minor; an outerplanar graph cannot contain K3,2 as a minor (These are not sufficient conditions for planarity and outerplanarity, but necessary). Conversely, every nonplanar graph contains either K3,3 or the complete graph K5 as a minor; this is Wagner's theorem. Kn,n is a Moore graph and a (n,4) -cage. 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. Km,n has a vertex covering number of min{m, n} and an edge covering number of max{m, n}. Km,n has a maximum independent set of size max{m, n}. Km,n has eigenvalues √nm , −√nm and 0; with multiplicity 1, 1 and n + m − 2 respectively. Km,n has eigenvalues n + m , n, m, and 0; with multiplicity 1, m − 1 , n − 1 and 1 respectively. Km,n has mn−1 nm−1 spanning trees. Km,n has a maximum matching of size min{m,n}. Kn,n has a proper n-edge-coloring corresponding to a Latin square.