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₁ be an unmatched node in M and let X₁ = {x₁}. We will construct two sequences of nodes x₁, x₂ ..., x_k and y₁, y₂ ..., 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₁..x_i and y₁..y_i-1 (i = 1 is the special case where we start with just x₁ and no y's), we have |∂{x₁...x_i}| ≥ i > |{y₁..y_i-1}|. So there is at least one node in ∂{x₁...x_i} - {y₁..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₁ or is matched with y_j-1. So working backwards from y_k we construct a sequence of nodes y_k = y'_mx'_my'_m-1x'_m-1...y'₁x'₁ = x₁ 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₁ 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.

CategoryMathNotes