Section 3.1 Introduction to Matchings
Recall from Definition 1.1.6 that a matching in a graph \(G\) is a set \(M\subseteq E(G)\) of edges with the property that every vertex of \(G\) is incident with at most one edge in \(M\text{.}\) In this chapter, we will attack optimization problems related to matchings in graphs from two angles: (1) using purely “combinatorial” methods and (2) by finding clever reductions to linear programming.
We start with the problem of finding a matching of maximum cardinality in a graph \(G\text{;}\) we call this quantity the matching number of \(G\) and denote it by \(\nu(G)\text{.}\) A fundamental notion in this problem is that of an alternating path. Given a matching \(M\) in a graph \(G\text{,}\) a path is said to be \(M\)-alternating if the edges of the path alternate between being in \(M\) and not in \(M\text{.}\) A vertex is \(M\)-saturated if it is contained in an edge of the matching. An \(M\)-alternating path is \(M\)-augmenting if the first and last edge of the path are not in \(M\) and its endpoints are \(M\)-unsaturated. It is fairly clear that if a matching contains an augmenting path, then you can get a larger matching by just swapping the edges along the path. As it turns out, any matching that does not have maximum size can be increased via an augmenting path.
Proof.
Clearly, if there exists an \(M\)-augmenting path, then we can swap the matching along the edges of that path to obtain a larger matching. On the other hand, suppose that \(M\) is not a maximum cardinality matching and let \(M'\) be any matching of larger cardinality than \(M\text{.}\) Let us think about the graph with edge set \(M\triangle M' = (M\setminus M')\cup(M'\setminus M)\) where the edges of \(M\setminus M'\) are red and the edges of \(M'\setminus M\) are blue. Then every vertex is incident with at most one edge of each colour. This easily implies that every component is either a path with alternating colours or a cycle of even length. Since \(|M'|>|M|\text{,}\) there must be more blue edges than red edges and so at least one of the components is a path that starts and ends with a blue edge. This path is an \(M\)-augmenting path in \(G\) and so the proof is complete.
As we have seen in linear programming, a powerful and pervasive idea in optimization is that of duality. In the case of matchings, a natural candidate for a dual is the notion of a vertex cover. Recall from Section 1.1 that a vertex cover is a set \(C\subseteq V(G)\) such that every edge of \(G\) has at least one endpoint in \(C\text{.}\) We let \(\tau(G)\) denote the minimum cardinality of a vertex cover and call this the vertex cover number of \(G\text{.}\) Lemma 1.1.10 in Section 1.1 can be thought of as a version of “weak duality” for matchings and vertex covers.
If we view Lemma 1.1.10 as being analogous to weak duality, one may naturally wonder whether strong duality holds; that is, does the matching number always equal the vertex cover number? Its not hard to see that the answer is “no” in general as an odd cycle of length \(2k+1\) has matching number \(k\) and vertex cover number \(k+1\text{.}\) However, as we shall see in the next section, \(\nu(G)=\tau(G)\) in the special case that \(G\) is bipartite.
Here is a YouTube video related to this section:
