In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets ${\displaystyle U}$ and ${\displaystyle V}$, that is, every edge connects a vertex in ${\displaystyle U}$ to one in ${\displaystyle V}$. Vertex sets ${\displaystyle U}$ and ${\displaystyle V}$ are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.

The two sets ${\displaystyle U}$ and ${\displaystyle V}$ may be thought of as a coloring of the graph with two colors: if one colors all nodes in ${\displaystyle U}$ blue, and all nodes in ${\displaystyle V}$ red, each edge has endpoints of differing colors, as is required in the graph coloring problem. In contrast, such a coloring is impossible in the case of a non-bipartite graph, such as a triangle: after one node is colored blue and another red, the third vertex of the triangle is connected to vertices of both colors, preventing it from being assigned either color.

One often writes ${\displaystyle G=(U,V,E)}$ to denote a bipartite graph whose partition has the parts ${\displaystyle U}$ and ${\displaystyle V}$, with ${\displaystyle E}$ denoting the edges of the graph. If a bipartite graph is not connected, it may have more than one bipartition; in this case, the ${\displaystyle (U,V,E)}$ notation is helpful in specifying one particular bipartition that may be of importance in an application. If ${\displaystyle |U|=|V|}$, that is, if the two subsets have equal cardinality, then ${\displaystyle G}$ is called a balanced bipartite graph. If all vertices on the same side of the bipartition have the same degree, then ${\displaystyle G}$ is called biregular.

When modelling relations between two different classes of objects, bipartite graphs very often arise naturally. For instance, a graph of football players and clubs, with an edge between a player and a club if the player has played for that club, is a natural example of an affiliation network, a type of bipartite graph used in social network analysis.

Another example where bipartite graphs appear naturally is in the (NP-complete) railway optimization problem, in which the input is a schedule of trains and their stops, and the goal is to find a set of train stations as small as possible such that every train visits at least one of the chosen stations. This problem can be modeled as a dominating set problem in a bipartite graph that has a vertex for each train and each station and an edge for each pair of a station and a train that stops at that station.

More abstract examples include the following:

Bipartite graphs may be characterized in several different ways:

In bipartite graphs, the size of minimum vertex cover is equal to the size of the maximum matching; this is Kőnig's theorem. An alternative and equivalent form of this theorem is that the size of the maximum independent set plus the size of the maximum matching is equal to the number of vertices. In any graph without isolated vertices the size of the minimum edge cover plus the size of a maximum matching equals the number of vertices. Combining this equality with Kőnig's theorem leads to the facts that, in bipartite graphs, the size of the minimum edge cover is equal to the size of the maximum independent set, and the size of the minimum edge cover plus the size of the minimum vertex cover is equal to the number of vertices.