Section 3.2 Matchings in Bipartite Graphs
Recall that a graph \(G\) is bipartite if its vertex set can be partitioned into two sets, say \(X\) and \(Y\text{,}\) such that every edge of the graph has one endpoint in \(X\) and one in \(Y\text{.}\) Such a pair \((X,Y)\) of sets is called a bipartition of \(G\text{.}\) Equivalently, a graph is bipartite if and only if it has no odd cycles. As promised in the previous section, we prove that the matching number of a bipartite graph is equal to its vertex cover number. We will first present a purely combinatorial proof but, later in Section 6.3, we will see how it can be derived directly from LP duality; see also Exercise 15.
Proof.
We already know that \(\nu(G)\leq \tau(G)\) from Lemma 1.1.10. So, it suffices to prove the reverse inequality. Let \(M\) be a matching in \(G\) of maximum cardinality. We will be done if we can construct a vertex cover \(C\) of cardinality \(M\text{.}\) Let \((X,Y)\) be the bipartition of \(G\) where we view the vertices of \(X\) as being on the “left” and the vertices of \(Y\) as being on the “right”.
Define \(U\) to be the set of vertices in \(X\) that are not saturated by \(M\) (which could be empty). Let \(W\) be the set of all vertices of \(G\) which can be reached by alternating paths starting at \(U\text{;}\) note that \(U\subseteq W\) by considering paths of length zero. Define
\begin{equation*}
C:=(X\setminus W)\cup (Y\cap W).
\end{equation*}
We claim that this is a vertex cover of cardinality \(|M|\text{.}\) First, let’s argue that it is a vertex cover. If it isn’t, then there must be an edge \(e\) from a vertex \(w\in X\cap W\) to a vertex \(y\in Y\setminus W\text{.}\) But what would this mean? Well, it would mean that there is an alternating path that starts at some \(u\in U\) and ends in \(w\text{.}\) Since \(u\) is unsaturated and \(u\) and \(w\) are both on the same side of the bipartition, the first edge of this path is not in \(M\) and the last edge of this path is in \(M\text{.}\) Since \(y\notin W\text{,}\) it cannot appear anywhere on this path. However, if we add the edge \(e=wy\) to the path, we get an alternating path that starts at \(u\) and ends at \(y\text{,}\) contradicting the fact that \(y\notin W\text{.}\) So, \(C\) must be a vertex cover.
Now, let us argue that \(|C|=|M|\text{.}\) To this end, we claim that every vertex of \(C\) is saturated and that every edge of \(M\) contains exactly one vertex of \(C\text{.}\) For the first statement, note that no vertex of \(X\setminus W\) can be unsaturated for, if it were, it would be in \(U\subseteq W\) and no vertex of \(y\in Y\cap W\) can be unsaturated because, if it were, then the alternating path from \(U\) to \(y\) would be augmenting, contradicting maximality of \(M\text{.}\) Finally, we show that every edge of \(M\) contains exactly one vertex of \(C\text{.}\) It contains at least one such vertex because \(C\) is a vertex cover. So, we are done unless there is an edge of \(M\) from \(x\in X\setminus W\) to \(y\in Y\cap W\text{.}\) However, if such a matching edge existed, then we could follow an alternating path from \(U\) to \(y\) and then follow the edge \(yx\) to get an alternating path from \(U\) to \(x\text{,}\) a contradiction.
A perfect matching in a graph is a matching that saturates every vertex. A close relative of Kőnig’s Theorem is Hall’s Theorem which provides a necessary and sufficient condition for a bipartite graph to have a perfect matching (or, more generally, have a matching that saturates one class of its bipartition). The neighbourhood of a vertex \(v\) in a graph \(G\) is the set \(N(v)=\{u: uv\in E(G)\}\text{.}\)
Theorem 3.2.2. Hall’s Theorem.
Let \(G\) be a bipartite graph with bipartition \((X,Y)\text{.}\) There exists a matching in \(G\) which saturates every vertex of \(X\) if and only if \(|N(S)|\geq |S|\) for every \(S\subseteq X\text{.}\)Proof.
In the rest of this section, we begin to explore the connection between matchings in bipartite graphs and linear programming. For a graph \(G\text{,}\) say that a vector in \((x_{uv}: uv\in E(G))\) indexed by the edges of \(G\) is a fractional matching in \(G\) if \(x\geq0\) and, for each vertex \(u\) of \(G\text{,}\) we have \(\sum_{v\in N(u)}x_{uv}\leq 1\text{.}\) If \(M\) is a matching in \(G\text{,}\) then the indicator vector of \(M\) is the vector \(x_M\) indexed by edges of \(G\) where \(uv\) entry is \(1\) if \(uv\in M\) and \(0\) otherwise. Clearly, the indicator vector for a matching is equivalent to an integer-valued fractional matching, and so fractional matchings can be seen as a generalization of matchings. A fractional matching \(x\) is called a fractional perfect matching if \(\sum_{v\in N(u)}x_{uv}= 1\) for all \(u\in V(G)\text{.}\)
The matching polytope of a graph \(G\text{,}\) denoted \(P_M\) is the convex hull of the indicator vectors of matchings in \(G\text{.}\) Similarly, the perfect matching polytope \(P_{PM}\) is the convex hull of indicator vectors of perfect matchings. Clearly, every element of the (perfect) matching polytope is a fractional (perfect) matching. However, the converse is not always true. Indeed, if \(G\) is an odd cycle, then the vector that assigns every edge to \(1/2\) is a fractional matching but it cannot be expressed a convex combination of indicator vector of matchings. However, as the next two lemmas show, if \(G\) is bipartite, then the converse is true.
Lemma 3.2.3. Birkhoff–von Neumann Theorem.
Every fractional perfect matching in a bipartite graph can be written as a convex combination of indicator vectors of perfect matchings.Proof.
Lemma 3.2.4.
Every fractional matching in a bipartite graph can be written as a convex combination of indicator vectors of matchings.Proof.
The next corollary follows immediately from the previous two lemmas.
Corollary 3.2.5.
If \(G\) is a bipartite graph, then the set of all fractional matchings of \(G\) is equal to the matching polytope of \(G\text{.}\) Also, the set of all fractional perfect matchings of \(G\) is equal to the perfect matching polytope of \(G\text{.}\)As an application of Corollary 3.2.5 and LP duality, we obtain the following weighted version of Kőnig’s Theorem known as Egerváry’s Theorem. Given a weight function \(w: E(G)\to \mathbb{R}\text{,}\) the weight of a set \(S\) of edges is defined to be \(w(S):=\sum_{e\in S}w(e)\text{.}\)
Theorem 3.2.6. Egerváry’s Theorem.
Let \(G\) be a bipartite graph and let \(w: E(G)\to \mathbb{R}\) be a weight function for the edges of \(G\text{.}\) Then the maximum weight of a matching in \(G\) is equal to the minimum value of \(\sum_{v\in V(G)}f(v)\) where \(f:V(G)\to[0,\infty)\) is a function such that \(f(u)+f(v)\geq w(uv)\) for every edge \(uv\in E(G)\text{.}\)Proof.
Let \(c\) be the vector indexed by edges of \(G\) where the \(uv\) entry is equal to \(w(uv)\text{.}\) Consider the linear program where the variables are the entries of \(x=(x_{uv}:uv\in E(G))\text{:}\)
\begin{align*}
\text{max} \amp\amp c^Tx\\
\text{subject to}\amp\amp \sum_{v\in N(u)}x_{uv} \leq 1\amp \text{ for each }u\in V(G)\\
\amp \amp x\geq0.
\end{align*}
In other words, this linear program is asking for a fractional matching of maximum weight. As we know from Corollary 3.2.5, the set of fractional matchings of \(G\) is equal to the matching polytope of \(G\text{.}\) So, the maximum of this linear program is achieved by one of the vertices of the matching polytope, which is an indicator vector of a matching. So, the maximum weight of a matching in \(G\) is equal to the value of this linear program. By strong duality for linear programming, it is also equal to the value of the following LP where \(y\) is indexed by the vertices of \(G\) and \(1\) denotes the all-ones vector:
\begin{align*}
\text{min} \amp\amp 1^Ty\\
\text{subject to}\amp\amp y_u + y_v\geq w(uv)\amp \text{ for each edge }uv\in E(G)\\
\amp \amp y\geq0.
\end{align*}
We are done by letting \(f(v)=y_v\) for all \(1\leq i\leq n\text{,}\) where \(y\) is an optimal vector for the above dual LP.
In the next section, we will present an explicit “combinatorial algorithm” which does not rely on linear programming as a “black box.”
Here are two YouTube videos related to this section:
