A graph (see GraphTheory) is a **bipartite graph** if its vertex set can be written as X∪Y and every edge is an element of X×Y. Alternatively, a graph is bipartite if it can be 2-colored (the vertices in the two color sets give X and Y). Yet another criterion is that a graph is bipartite if and only if it does not contain a cycle with an odd number of edges.

# 1. Bipartite matching

Bipartite graphs are often used to model assignment problems, where the vertices of the left-hand side X represent things that need to be assigned, the vertices of the right-hand side Y represent places to put them, and an edge indicates compatibility. A **complete bipartite matching** is a subset of the edges of a bipartite graph such that every node is the endpoint of exactly one edge: such a matching corresponds to an assignment that assigns every object and fills every niche (it also implies |X|=|Y|). This is a special case of a **matching**, which is a subset of the edges of an arbitrary graph that hits each vertex at most once, and a **maximal matching**, a matching that is maximal under inclusion---i.e., one where you can't add any more edges without making it no longer be a matching.

Because of the application to assignment, much is known about bipartite matching. In particular, there is a characterization of exactly which bipartite graphs have a complete matching.

- Hall's Theorem
- Let G = (X∪Y, E) be a bipartite graph, and for each A⊆X define ∂A = {y∈Y: ∃x∈A such that xy∈E}. Then G has a complete matching if and only if |∂A| ≥ |A| for all A⊆X.
- Proof
If there is some A with |∂A| < |A| we are clearly in trouble, so the main thing is to show that |∂A| ≥ |A| is sufficient. We do so by showing that when the condition holds, any matching M with |M| < |X| can be extended to a matching of size |M|+1. The procedure is as follows: Let x

_{1}be an unmatched node in M and let X_{1}= {x_{1}}. We will construct two sequences of nodes x_{1}, x_{2}..., x_{k}and y_{1}, y_{2}..., y_{k}such that y_{i}is matched to x_{i+1}when i < k, y_{k}is unmatched, and y_{i}is adjacent to at least one node x_{j}with j ≤ i. The construction proceeds as follows: given x_{1}..x_{i}and y_{1}..y_{i-1}(i = 1 is the special case where we start with just x_{1}and no y's), we have |∂{x_{1}...x_{i}}| ≥ i > |{y_{1}..y_{i-1}}|. So there is at least one node in ∂{x_{1}...x_{i}} - {y_{1}..y_{i-1}}; pick that node and call it y_{i}. If y_{i}is unmatched, we are done. Otherwise, let x_{i+1}be y_{i}'s match in M and repeat. Now we have that each y_{i}is adjacent to some x_{j}with j ≤ i, and that that x_{j}is either x_{1}or is matched with y_{j-1}. So working backwards from y_{k}we construct a sequence of nodes y_{k}= y'_{m}x'_{m}y'_{m-1}x'_{m-1}...y'_{1}x'_{1}= x_{1}where each y'_{m}is adjacent to x'_{m}but not matched to it in M and each y' or x' except y_{k}and x_{1}is matched in M (such a sequence is called an**augmenting path**. So by deleting all of the edges in M between some y' and x' and replacing them with edges between y'_{i}and x'_{i}for each i, we remove m-1 edges and add m, increasing the size of the matching by 1.

A useful corollary of Hall's Theorem is that even if there is no complete matching, there is still a matching that matches all but max_{A} |A|-|∂A| nodes in X. The essential idea is that we can make Hall's condition hold by adding exactly that many new nodes to Y that can be matched with any node in X. The nodes that are matched with the new nodes in the resulting complete matching become the unmatched losers in the original graph.