Graph, bipartite

From Encyclopedia of Mathematics
Jump to: navigation, search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

2020 Mathematics Subject Classification: Primary: 05C [MSN][ZBL]

bichromatic graph

A graph whose set $V$ of vertices can be partitioned into two disjoint sets $V'$ and $V''$ (i.e. $V=V'\cup V''$, $V'\cap V''=\emptyset$) so that each edge connects some vertex of $V'$ with some vertex of $V''$. A graph is bipartite if and only if all its simple cycles have even length. Another frequently used definition of a bipartite graph is a graph in which two subsets $V'$ and $V''$ of vertices (parts) are given in advance. Bipartite graphs are convenient for the representation of binary relations between elements of two different types — e.g. the elements of a given set and a subset of it yield the relation of "membership of an element to a subset", for executors and types of jobs one has the relation "a given executor can carry out a given job", etc.

An important problem concerning bipartite graphs is the study of matchings, that is, families of pairwise non-adjacent edges. Such problems occur, for example, in the theory of scheduling (partitioning of the edges of a bipartite graph into a minimal number of disjoint matchings), in the problem of assignment (finding the maximum number of elements in a matching), etc. The cardinality of the maximum matching in a bipartite graph is

$$|V'|-\max_{A'\subseteq V'}(|A'|-|V''(A')|),$$

where $V''(A')$ is the number of vertices of $V''$ adjacent to at least one vertex of $A'$. A complete bipartite graph is a bipartite graph in which any two vertices belonging to different subsets are connected by an edge (e.g. the graph $K_{3,3}$, see Graph, planar, Figure 1).

A generalization of the concept of a bipartite graph is the concept of a multipartite or $k$-partite graph, i.e. a graph in which the vertices are partitioned into $k$ subsets so that each edge connects vertices belonging to different subsets.


[1] O. Ore, "Theory of graphs" , Amer. Math. Soc. (1962)


The complete bipartite graph on vertex sets of size $a,b$ is denoted $K_{a,b}$. Similarly the complete multipartite graph on $k$ vertex sets of sizes $a_1,\ldots,a_k$ is denoted $K_{a_1,\ldots,a_k}$. The complement of a complete multipartite $K_{a_1,\ldots,a_k}$ is a disjoint union of complete graphs $K_{a_1} \sqcup \cdots \sqcup K_{a_k}$.


[a1] F. Harary, "Graph theory" , Addison-Wesley (1969) pp. Chapt. 9
[a2] R.J. Wilson, "Introduction to graph theory" , Longman (1985)
[b1] Biggs, Norman Algebraic graph theory 2nd ed. Cambridge University Press (1994) ISBN 0-521-45897-8 Zbl 0797.05032
How to Cite This Entry:
Graph, bipartite. Encyclopedia of Mathematics. URL:,_bipartite&oldid=54676
This article was adapted from an original article by V.B. Alekseev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article