Thursday, January 9, 2014

Bipartite graphs and perfect matching

1Matchings¶

1.1Definitions¶

Let $G = (V, E)$ be some graph. A matching in $G$ is a set of vertex-disjoint edges (so that each vertex is incident to at most one edge in $M$).

A vertex $v \in V$ is matched by $M$ if it's incident to some edge in $M$.

A path $P$ in $G$ is alternating with respect to $M$ if the edges of $P$ alternate between being in $M$ and not being in $M$.

An alternating path is augmenting with respect to $M$ if it is of odd length, and the two endpoints are unmatched.

1.2Maximum cardinality¶

Theorem: a matching $M$ is at maximum cardinality in $G$ if and only if $G$ contains no augmenting path with respect to $M$.

Proof: $(\Rightarrow)$ We want to show that if $G$ contains an augmenting path with respect to $M$, then $M$ is not maximal (i.e., there exists another valid matching within $G$ containing a greater number of edges). This direction of the proof is simple - we can just flip the matched/unmatched status of the edges in the augmenting path ("augment" the path, in other words) so that the endpoints are now matched. This results in one more edge in our new matching than in the original matching.

Specifically, we create a new matching $M' = (M \cup (P \setminus M)) \setminus (M \cap P)$, which has a greater cardinality than $M$, as $|M'| = |M| + 1$.

$(\Leftarrow)$: Suppose $M$ is not maximal. Let $M^*$ be a maximal matching. Consider the symmetric difference of $M$ and $M^*$: $M' = M \oplus M^* = (M \cup M^*) \setminus (M \cap M^*) = (M \setminus M^*) \cup (M^* \setminus M)$ (i.e., all the edges that are in exactly one of the matchings; analogous to the XOR operator for bits). Now, each vertex in the graph must have degree $\leq 1$ with respect to $M$, and degree $\leq 1$ with respect to $M^*$. Thus, each vertex in the graph must have degree $\leq 2$ with respect to $M'$. It's not possible to have a vertex with degree 3 wrt $M'$, because then it would have to be adjacent to at least two edges that are both in $M$ or $M^*$, which is not possible by the definition of a matching.

It's easy to see that a graph whose vertices all have degree $\leq 2$ consists exclusively of disjoint paths and cycles. Consider the cardinality of these paths and cycles. Since their edges must alternate between being in $M$ and being in $M^*$, all of the cycles must have even length. Furthermore, there can be no odd-length path ending in edges in $M$, because then that would be an augmenting path, and we could make $M^*$ even larger simply by reversing the $M$ and $M^*$ edges on this path (so all the $M$ edges would now be part of $M^*$, and vice versa); this would contradict the premise that $M^*$ is maximal.

Thus, $M'$ consists solely of even-length paths, even-length cycles, and odd-length paths ending in edges found in $M^*$ (but not in $M$). Clearly, the even-length paths and cycles have the same number of edges from $M$ as they do edges from $M^*$. The odd-length paths, however, have one additional $M^*$ edge compared to its $M$ edges. Furthermore, we know that there must be at least one such odd path, since $M^*$ is maximal but $M$ is not, so $M^*$ must have at least one more edge than $M$. But then this odd path is augmenting with respect to $M$, which is exactly what we needed to show. $\blacksquare$

1.3Bipartite graphs¶

The above applied to graphs in general. From now on, we will focus on a specific type of graph: bipartite graphs, in which the vertices can be partitioned (separated into two groups) such that every edge has exactly one endpoint in each of the partitions.

A graph is bipartite if and only if it has no odd cycles. Proof omitted, just presented as fact.

1.3.1Hall's theorem¶

This theorem tells us when a bipartite graph has a perfect matching. First, we define the term perfect matching: a perfect matching is a matching that covers every vertex. Next, we define the neighbourhood of some set of vertices $A \subseteq V$: $\Gamma(A)$ is the set of vertices adjacent to at least one vertex in $A$.

Theorem: a bipartite graph with equal-sized partitions $X$, $Y$ has a perfect matching $\iff$ for all $A \subseteq X$, $|\Gamma(A)| \geq |A|$ (this is called Hall's condition).

Proof: $(\Rightarrow)$ Suppose Hall's condition does not hold. That is, there exists some $A \subseteq X$ such that $|\Gamma(A)| < |A|$. But then not every vertex in $A$ can be matched, by the pigeonhole principle. Done.

$(\Leftarrow)$ Suppose Hall's condition does hold. Take the biggest matching that we can find in this graph, and call it $M$. If $|M| = |X| = |Y|$, then $M$ is clearly a perfect matching (as it contains all the edges/vertices) and so we'd be done, so we assume that $|M| < |X|$. Then, there exists some $x_1 \in X$ such that $x_1$ is unmatched by $M$. By Hall's condition, $|\Gamma(\{x_1\})| \geq |\{x_1\}| = 1$ so the neighbourhood of $x_1$ has at least one vertex. Thus $x_1$ is adjacent to at least one edge. So there exists some $y_1 \in Y$ such that $y_1 \in \Gamma(\{x_1\})$.

Now, if $y_1$ were unmatched, then $M \cup (x_1 \cup y_1)$ would be a bigger matching than $M$. In other words, we could have just included the edge between $x_1$ and $y_1$ in $M$ in the first place. So we can assume that $y_1$ is matched. Let's call the vertex that $y_1$ is matched to $x_2$. Again, by Hall's condition, $|\Gamma(\{x_1, x_2\})| \geq |\{x_1, x_2\}| = 2$, so there are at least 2 neighbours for those vertices. We've only found one so far, $y_1$. Thus there must be some $y_2 \in Y$ such that $y_2 \in \Gamma(\{x_1, x_2\})$ with $y_2 \neq y_1$.

Now, if $y_2$ is unmatched, then there exists an augmenting path from $x_1$ to $y_2$ - either a direct edge, or a 3-edge path - so we could just augment that to get a bigger matching. This contradicts the maximality of $M$! So we assume that $y_2$ is matched to some $x_3$. By Hall's condition, the neighbourhood of $\{x_1, x_2, x_3\}$ contains at least 3 vertices, thus there is some new vertex $y_3 \in Y$ matched to $x_3$. This argument continues in this fashion until we've exhausted all of $X$ (which must occur eventually, as $X$ is finitely large, showing that this algorithm terminates), at which point we get a perfect matching between $X$ and $Y$.

An alternative, and more rigorous, proof for the above uses induction on $|X|$. In the base case, if $|X| = 1$, then $|Y| = 1$ so we just include the edge between the vertex in $X$ and the vertex in $Y$ in the matching. (Such an edge must exist, by Hall's condition.)

For the induction hypothesis, we assume that if Hall's condition is true, then there exists a perfect matching when $|X| = k$.

Next, we perform the induction step, for $|X| = k+1$. We break down our analysis into two separate cases:

Case 1: $|\Gamma(A)| \geq |A|+1$ for all $A \subseteq X$ (i.e., the neighbourhood to each subset of $X$ is strictly larger than the subset itself). Take some edge $(x, y)$. Consider the graph $G'$, which is identical to $G$ except for the fact that it removes the vertices $x$ and $y$ (and the edge between them). Then $X'$, the left partition of $G'$, has $k$ elements. Then we just need to check that Hall's condition holds for $X'$. Well, since we have a stricter version of Hall's condition for $G$, then since we only got rid of one vertex to get $G'$, the non-strict (canonical) version of Hall's condition does indeed hold. Thus $G'$ has a perfect matching $M'$, and we can add the $(x, y)$ edge to $M'$ to get a perfect matching for $G$.

Case 2: $\exists A \subset X$ such that $|\Gamma(A)| = |A|$. Consider $G_1$, which is partitioned into $A$ and $\Gamma(A)$, and $G_2$, the complement of $G_1$ in the graph $G$. Now, Hall's condition must hold for $G_1$ and $G_2$, by the induction hypothesis.

Now consider $G_2$. Take $A' \subset (X \setminus A)$. We want to show that $|\Gamma_{G_2}(A')| \geq |A'|$. Well, if this is not true, then it must be that

$$\begin{align} |\Gamma_G(A \cup A')| & = |\Gamma_G(A)| + |\Gamma_{G_2}(A')| \\ & = |A| + |\Gamma_{G_2}(A')| \\ & < |A| + |A'| \\ & = |A \cup A'| \end{align}$$

which is a contradiction to the fact that Hall's condition holds for $G$, the original graph. Thus there exist perfect matchings in $G_1$ and $G_2$, and if we combine these matchings we get a perfect matching for $G$. $\blacksquare$