In the

mathematical Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

field of

graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, a complete bipartite graph or biclique is a special kind of

bipartite graph In the mathematics, mathematical field of graph theory, a bipartite graph (or bigraph) is a Graph (discrete mathematics), graph whose vertex (graph theory), vertices can be divided into two disjoint sets, disjoint and Independent set (graph theo ...

where every vertex of the first set is connected to every vertex of the second set..
Electronic edition
page 17. Graph theory itself is typically dated as beginning with

Leonhard Euler Leonhard Euler ( ; ; ; 15 April 170718 September 1783) was a Swiss polymath who was active as a mathematician, physicist, astronomer, logician, geographer, and engineer. He founded the studies of graph theory and topology and made influential ...

's 1736 work on the

Seven Bridges of Königsberg The Seven Bridges of Königsberg is a historically notable problem in mathematics. Its negative resolution by Leonhard Euler, in 1736, laid the foundations of graph theory and prefigured the idea of topology. The city of Königsberg in Prussia ...

. However,

drawing Drawing is a Visual arts, visual art that uses an instrument to mark paper or another two-dimensional surface, or a digital representation of such. Traditionally, the instruments used to make a drawing include pencils, crayons, and ink pens, some ...

s of complete bipartite graphs were already printed as early as 1669, in connection with an edition of the works of

Ramon Llull Ramon Llull (; ; – 1316), sometimes anglicized as ''Raymond Lully'', was a philosopher, theologian, poet, missionary, Christian apologist and former knight from the Kingdom of Majorca. He invented a philosophical system known as the ''Art ...

edited by

Athanasius Kircher Athanasius Kircher (2 May 1602 – 27 November 1680) was a German Society of Jesus, Jesuit scholar and polymath who published around 40 major works of comparative religion, geology, and medicine. Kircher has been compared to fellow Jes ...

. Llull himself had made similar drawings of

complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices i ...

s three centuries earlier..

Definition

A complete bipartite graph is a graph whose vertices can be partitioned into two subsets and 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

such that for every two vertices and, is an edge in . A complete bipartite graph with partitions of size and , is denoted ; every two graphs with the same notation are

isomorphic In mathematics, an isomorphism is a structure-preserving mapping or morphism between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between the ...

Examples

* For any , is called a

star A star is a luminous spheroid of plasma (physics), plasma held together by Self-gravitation, self-gravity. The List of nearest stars and brown dwarfs, nearest star to Earth is the Sun. Many other stars are visible to the naked eye at night sk ...

. All complete bipartite graphs which are

trees In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, e.g., including only woody plants with secondary growth, only p ...

are stars. ** The graph is called a

claw A claw is a curved, pointed appendage found at the end of a toe or finger in most amniotes (mammals, reptiles, birds). Some invertebrates such as beetles and spiders have somewhat similar fine, hooked structures at the end of the leg or Arthro ...

, and is used to define the

claw-free graph In graph theory, an area of mathematics, a claw-free graph is a graph that does not have a claw (graph theory), claw as an induced subgraph. A claw is another name for the complete bipartite graph K_ (that is, a star graph comprising three edges, ...

s. * The graph is called the

utility graph In economics, utility is a measure of a certain person's satisfaction from a certain state of the world. Over time, the term has been used with at least two meanings. * In a normative context, utility refers to a goal or objective that we wish ...

. 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 . * 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 In information science, formal concept analysis (FCA) is a principled way of deriving a ''concept hierarchy'' or formal ontology from a collection of objects and their properties. Each concept in the hierarchy represents the objects sharing som ...

Properties

*Given a bipartite graph, testing whether it contains a complete bipartite subgraph for a parameter is an

NP-complete In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...

problem. *A

planar graph In graph theory, a planar graph is a graph (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. ...

cannot contain as a

minor Minor may refer to: Common meanings * Minor (law), a person not under the age of certain legal activities. * Academic minor, a secondary field of study in undergraduate education Mathematics * Minor (graph theory), a relation of one graph to an ...

; an

outerplanar graph In graph theory, an outerplanar graph is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing. Outerplanar graphs may be characterized (analogously to Wagner's theorem for planar graphs) by the two f ...

cannot contain as a minor (These are not

sufficient condition In logic and mathematics, necessity and sufficiency are terms used to describe a conditional or implicational relationship between two statements. For example, in the conditional statement: "If then ", is necessary for , because the truth of ...

s for planarity and outerplanarity, but necessary). Conversely, every nonplanar graph contains either or the

as a minor; this is

Wagner's theorem In graph theory, Wagner's theorem is a mathematical forbidden graph characterization of planar graphs, named after Klaus Wagner, stating that a finite graph is planar if and only if its graph minor, minors include neither ''K''5 (the complete g ...

. *Every complete bipartite graph. is a

Moore graph In graph theory, a Moore graph is a regular graph whose girth (the shortest cycle length) is more than twice its diameter (the distance between the farthest two vertices). If the degree of such a graph is and its diameter is , its girth must ...

and a -

cage A cage is an enclosure often made of mesh, bars, or wires, used to confine, contain or protect something or someone. A cage can serve many purposes, including keeping an animal or person in captivity, capturing an animal or person, and displayi ...

. *The complete bipartite graphs and have the maximum possible number of edges among all

triangle-free graph In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with ...

s with the same number of vertices; this is Mantel's theorem. Mantel's result was generalized to -partite graphs and graphs that avoid larger

cliques A clique ( AusE, CanE, or ; ), in the social sciences, is a small group of individuals who interact with one another and share similar interests rather than include others. Interacting with cliques is part of normative social development regardle ...

as subgraphs in

Turán's theorem In graph theory, Turán's theorem bounds the number of edges that can be included in an undirected graph that does not have a clique (graph theory), complete subgraph of a given size. It is one of the central results of extremal graph theory, an a ...

, and these two complete bipartite graphs are examples of

Turán graph The Turán graph, denoted by T(n,r), is a complete multipartite graph; it is formed by partitioning a set of n vertices into r subsets, with sizes as equal as possible, and then connecting two vertices by an edge if and only if they belong to di ...

s, the extremal graphs for this more general problem. *The complete bipartite graph has a vertex covering number of and an

edge covering number Edge or EDGE may refer to: Technology Computing * Edge computing, a network load-balancing system * Edge device, an entry point to a computer network * Adobe Edge, a graphical development application * Microsoft Edge, a web browser developed by ...

of *The complete bipartite graph has a

maximum independent set In mathematical analysis, the maximum and minimum of a function are, respectively, the greatest and least value taken by the function. Known generically as extremum, they may be defined either within a given range (the ''local'' or ''relative ...

of size *The

adjacency matrix In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph (discrete mathematics), graph. The elements of the matrix (mathematics), matrix indicate whether pairs of Vertex (graph theory), vertices ...

of a complete bipartite graph has eigenvalues , and 0; with multiplicity 1, 1 and respectively. *The

Laplacian matrix In the mathematical field of graph theory, the Laplacian matrix, also called the graph Laplacian, admittance matrix, Kirchhoff matrix, or discrete Laplacian, is a matrix representation of a graph. Named after Pierre-Simon Laplace, the graph Lap ...

of a complete bipartite graph has eigenvalues , , , and 0; with multiplicity 1, , and 1 respectively. *A complete bipartite graph has

spanning tree In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is no ...

s. *A complete bipartite graph has a

maximum matching Maximum cardinality matching is a fundamental problem in graph theory. We are given a graph , and the goal is to find a matching containing as many edges as possible; that is, a maximum cardinality subset of the edges such that each vertex is a ...

of size *A complete bipartite graph has a proper -edge-coloring corresponding to a

Latin square Latin ( or ) is a classical language belonging to the Italic branch of the Indo-European languages. Latin was originally spoken by the Latins in Latium (now known as Lazio), the lower Tiber area around Rome, Italy. Through the expansion o ...

. *Every complete bipartite graph is a

modular graph In graph theory, a branch of mathematics, the modular graphs are undirected graphs in which every three vertices , , and have at least one ''median vertex'' that belongs to shortest paths between each pair of , , and .Biclique-free graph In graph theory, a branch of mathematics, a -biclique-free graph is a graph that has no (complete bipartite graph with vertices) as a subgraph. A family of graphs is biclique-free if there exists a number such that the graphs in the family ar ...

, a class of sparse graphs defined by avoidance of complete bipartite subgraphs *

Crown graph In graph theory, a branch of mathematics, a crown graph on vertices is an undirected graph with two sets of vertices and and with an edge from to whenever . The crown graph can be viewed as a complete bipartite graph from which the edges ...

, a graph formed by removing a

perfect matching In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph with edges and vertices , a perfect matching in is a subset of , such that every vertex in is adjacent to exact ...

from a complete bipartite graph *

Complete multipartite graph In graph theory, a part of mathematics, a -partite graph is a graph whose vertices are (or can be) partitioned into different independent sets. Equivalently, it is a graph that can be colored with colors, so that no two endpoints of an edge h ...

, a generalization of complete bipartite graphs to more than two sets of vertices * Biclique attack

References

{{reflist, 30em Parametric families of graphs