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. Mathematics is commonly defined as the study of patterns of structure, change, and space; more informally, one might say it is the study of figures and numbers. Mathematical knowledge is constantly growing, through research and application, but mathematics itself is not usually considered a natural science. ... A pictorial representation of a graph In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. ... In the mathematical field of graph theory, a bipartite graph is a special graph where the set of vertices can be divided into two disjoint sets and such that no edge has both end-points in the same set. ... This article just presents the basic definitions. ...

Definition

A complete bipartite graph G: = (V₁ + V₂,E) is a bipartite graph such that for any two vertices and v₁v₂ is an edge in G. The complete bipartite graph with partitions of size and is denoted K_m,n.

Examples

Properties

• Given a bipartite graph, finding its complete bipartite subgraph K_m,n with maximal number of edges is a NP-complete problem.
• A planar graph cannot contain K_3,3 as a minor; an outerplanar graph cannot contain K_3,2 as a minor (These are not sufficient conditions for planarity and outerplanarity, but necessary).
• A complete bipartite graph K_n,n is a Moore graph and a (n − 1,4)-cage
• A complete bipartite graph K_n,n or K_{n,n + 1} is a Turán graph
• A complete bipartite graph K_m,n has a vertex covering number of min{m,n} and an edge covering number of max{m,n}
• A complete bipartite graph K_m,n has a maximum independent set of size max{m,n}
• A complete bipartite graph K_m,n has a maximum matching of size min{m,n}
• A complete bipartite graph K_n,n has a proper n-edge-coloring
• The last two results are corollaries of the Marriage Theorem as applied to a k-regular bipartite graph

In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use... // In graph theory, a planar graph is a graph that can be drawn (mathematicians say can be embedded in the plane) so that no edges intersect. ... In graph theory, a graph H is called a minor of the graph G if H is isomorphic to a graph that results from a subgraph of G by zero or more edge contractions. ... In logic, the words necessary and sufficient describe relations that hold between propositions or states of affairs, if one is conditional on the other. ... In graph theory, a Moore graph is a regular graph of degree d and diameter k whose number of vertices equals the upper bound An equivalent definition of a Moore graph is that it is a graph of diameter k with girth 2k + 1. ... The Tutte (3,8)-cage. ... The Turan graph T(n,r) is the complete r-partite graph with n vertices whose partite sets differ in size at most 1. ... In the mathematical discipline of graph theory a covering for a graph is a set of vertices (or edges) so that the elements of the set are close (adjacent) to all edges (or vertices) of the graph. ... In the mathematical discipline of graph theory a covering for a graph is a set of vertices (or edges) so that the elements of the set are close (adjacent) to all edges (or vertices) of the graph. ... In graph theory, an independent, or stable, set in a graph G, which contains vertices V, is a set of vertices V (a subset of V) such that for every two vertices in V, there is no edge connecting the two. ... This article is about mathematical matchings. ... In graph theory, as with its vertex counterpart, an edge coloring of a graph, when mentioned without any qualification, is always assumed to be a proper coloring of the edges, meaning no two adjacent edges are assigned the same color. ... A theorem is a statement which can be proven true within some logical framework. ... In mathematics, the marriage theorem (1935), usually credited to mathematician Philip Hall, is a combinatorial result that gives the condition allowing the selection of a distinct element from each of a collection of subsets. ... In graph theory, a regular graph is a graph where each vertex has the same number of neighbors, i. ...

See also

• bipartite graph