The Computer Scientist's Guide to Graph Theory, ep. 02
An introduction to matchings
Hi there! This post is a collaboration with Alejandro, taken directly from our upcoming book, The Hitchhiker's Guide to Graphs. This project grew out of our series in graph theory here, aiming to focus on the algorithmic aspects as well. We'll even implement our custom graph library from scratch.
The book is already available in early access, with instant updates to the content as we write it.
Alejandro is one of my favorite writers and one of my original inspirations for starting to talk about mathematics online. We complement each other in knowledge and style: He is a master of computer science and algorithms, and I make the necessary theoretical background as clear as possible.
If you would like to see what's the book like, check out our introductory series on graph theory:
Episode 00: What do your brain, your friends, and the city you live in have in common
Episode 01: Running into the woods: trees, forests, and spanning subgraphs
The local book club is organizing a community workshop. Each of the members will give a small talk about one specific book. The problem is, some of the members have read many of the same books, and we don’t want any redundancy! Every person must be assigned at most one book to present, and no book can be presented twice.
What’s the best we can do? In other words, if we know the books that each person has read, how can we guarantee that the maximum number of books get assigned to someone?
This is a example of a graph matching problem. You can model it naturally with a special type of graph called a bipartite graph, which intuitively is just a graph of two distinct types of vertices (people and books in this case) where no edges go between vertices of the same type.
A matching in such a graph is just a selection of pairs of connected vertices (or edges) such that no vertex is selected more than once.
Matching can occur in general graphs, but we most often use bipartite graphs because they model the nature of the majority of these problems where we have two different types of things related among them. The most common question in matching problems is finding the maximum possible matching, that is, the one that contains the most disjoint edges.
However, we can ask many more questions:
How can we tell if a matching is a maximum possible matching?
Is there more than one maximum matching?
Can we match all vertices of one type? (In our example, can we ensure that all books are presented?)
Can we match all vertices of both types? (In our example, can we ensure that no person is left out of the workshop?)
This is the third lecture in the Computer Scientist’s Guide to Graph Theory. In this issue we will study the problem of matching in general and bipartite graphs, and come up with theorems that let us answer all of the above questions. (And some others.)
This lecture relies heavily on concepts and results from the previous entries in the series, so we recommend you read those first if you haven’t.
Matching essentials
Let’s start with matchings in general, beginning with a formal definition.
Definition 1. In the graph G = (V, E) a matching M is a subset of pairwise disjoint edges (M ⊆ E), that is, no two edges in M share a common vertex.
Notice that our definition relies on selecting edges, indicating the pairs of vertices matched. The following are examples of valid and invalid matchings in an arbitrary graph.
To study matchings and their properties, we will be interested in analyzing which vertices are participating in a given matching. Let’s give them a name.
Definition 2: Given a graph G and a matching M, a vertex v ∈ V(G) is said to be M-matched if there is some edge vw ∈ M that touches v. Otherwise, the vertex is M-unmatched.
(Notice that by the definition of matching, if v is M-matched then there is exactly one edge in M that touches it.)
Armed with our essential definitions, we can now tackle the big problem: finding a maximum matching.
Maximum matching
Let’s kick off with a quick definition to see what do we mean by maximum. This will be pretty obvious for many of you but it’s better to put in on ink (or electrons, in this case).
Definition 3: In a graph G, a matching M* of size (number of edges) |M*| is maximum if there is no other matching M such that |M| > |M*|.
(Note that this definition doesn’t preclude the possibility of having more than one maximum matching.)
What makes a matching maximum? Of course, the most evident characteristic of a maximum matching is that no other matching has more edges. But that is precisely our definition. What we want is a necessary and sufficient condition that explains why a matching is maximum, in terms of its inner composition.
One way to start looking at this problem is to ask when can we make a matching any bigger. Evidently, any matching that can be grown — by adding another edge that is pairwise disjoint with the whole matching — cannot be maximum. It makes sense to ask then, can we just pick disjoint edges at will and find a maximum match?
Unfortunately, math is rarely that simple. Depending on the order in which we pick the edges, we can get stuck with a matching M that cannot be grown any further, but it is still smaller than the maximum M*. Here are two examples of matchings built iteratively until no more edges can be added, one of which is not a maximum.
This type of objects — that cannot be increased without losing their definition — are called maximals and studying them often offers useful insights for understanding where we can find the maximum(s).
Back to our example, it is clear that we cannot turn our maximal matching into a maximum matching juts by adding new edges, but we can do something slightly more clever. Notice that we can transform the maximal into the maximum by swapping alternating edges in the following way:
What we did was find something called an M-alternating path, that is, a path that alternates between edges in M and edges not in M. In such a path, you can always swap the edges and still obtain a valid matching, because since edges alternate, there is no change you’ll pick two edges that touch the same vertex. And even better, if that path starts and ends with edges that are not in M, it is called an M-augmenting path, because swapping it will give you a bigger, but still valid matching!
So, once we have a maximal matching —by randomly selecting disjoint edges—, we may still be able to grow it further by finding an M-augmenting path. However, can we always guarantee that we will eventually reach a maximum matching? It turns out that we can! This will be our first theorem of the day. Buckle up because the proof is going to be way larger than anything we’ve done so far.
Theorem 1. In an arbitrary graph G, a matching M is maximum if and only if there are no M-augmenting paths.
Proof: There are two sides to this proof, an easy one and a hard one. The easy part is showing that if M is maximum, we cannot have an M-augmenting path. We will do this by proving the contrapositive:
If there is an M-augmenting path P, then M is not maximum.
This is obvious because we already showed how we can build a bigger matching M’ by swapping all edges from P that are not in M with all the edges from P that are in M.
This will never create an invalid matching because any two edges new added cannot touch the same vertex (as they are separated by at least one edge in P), and none of the new edges can touch an M-matched vertex v that is matched by an edge not in P, because that would imply we had a previous edge in P touching that same vertex, thus M couldn’t be a valid matching.
The second part is proving that if we can’t find an M-augmenting path then M must be maximum. Again, we will do this by proving the contrapositive:
If M is not maximum, we can always find an M-augmenting path.
Let’s show how we can build this path. Since M is not maximum, there must another, maximum matching M*, such that |M*| > |M|. That is, M* contains at least one edge more than M.
We will merge the edges in both matchings to construct an M-augmenting path for M, but we must be clever about it, because both matchings can have some common edges. Instead, we will take exactly the set of edges that are in one but no both matchings. Formally, we call this operation a symmetric difference, denoted as
M Δ M* = (M − M*) ∪ (M* − M).
Next, we will consider the subgraph H induced by these edges. Let’s see how such a subgraph might look in an example graph.
Notice that, in H, all connected components must be either paths or cycles, that is, every vertex has deg(v) ≤ 2. That is because every vertex can have at most two incident edges — one from M and one from M*, otherwise they wouldn’t be valid matchings.
Furthermore, every connected component has edges that alternate between M and M*, again, because otherwise we would have two edges in matching touching the same vertex. This implies that every cycle in H (if there are any) must have an even length, thus exactly the same number of edges from M and M*.
But, there are in total more edges from M* than M in H, because M* is bigger — it’s a maximum matching, after all. Thus, there has to be some path in H that has more edges from M* than M, and such a path will be our M-augmenting path.
We still need to prove that this path indeed is M-augmenting, but we already know the path is M-alternating by construction, so we only need to prove that the two extreme vertices (call them v and u) are not M-matched. But that has to be the case, for otherwise there would be an edge vx in M that is not in H, which means vx must be in M*, which would imply there are two edges in M* touching v, making M* an invalid matching (the same analysis can be done with u.) ◼
Phew! If this proof seemed intense, is because it is!
Before moving on, notice that this theorem looks a bit like cheating, because we want to find a maximum matching, but we used the fact that one such matching must exist during the proof, as if we had already found it! This is a common move in proving math theorems: one assumes one already knows the answer, and derives what must be true in order to get there.
But once finished, we have a theorem that can tell us when any matching is maximum without having to know a maximum matching beforehand. Just look for augmenting paths, and if you can’t find one, you’re done!
(By the way, that is a terrible algorithm! There are far more efficient algorithms for finding maximum matchings in general graphs, but that’s a story for another series.)
Now that we know how maximum matchings appear in arbitrary graphs, we can move on to finding maximum matchings in bipartite graphs. But first, we’ll need to understand these a little better.
Bipartite graphs
We already have the intuitions in place for bipartite graphs, so let’s formally define them.
Definition 4. A bipartite graph G = (X∪Y, E) is a graph whose vertices can be partitioned into two sets V = X ∪ Y such that for all uv ∈ E, it follows that u ∈ X, v ∈ Y.
The following are some examples of bipartite graphs in the wild.
Note that it may not be trivial to recognize that a graph is bipartite if we don’t know beforehand how the vertices are partitioned. Since, obviously, we can’t rely on a helpful drawing most of the time, we need a principled, graph-theoretic way of determining when an arbitrary graph is indeed bipartite.
Looking at the previous examples, one intuition you get is that all cycles in these graphs have an even length (in number of edges). Can we turn this into a necessary and sufficient condition? Well, yes!
Theorem 2. (Berge) A graph G is bipartite if and only if all cycles have an even number of edges.
Proof: Like all necessary and sufficient conditions, we need to prove the statement in two directions.
First, for the necessary condition, let’s assume we have a bipartite graph G, with the vertices partitioned into X and Y. Let’s take an arbitrary cycle C in this graph, without loss of generality let’s say it starts with a vertex in x₁ ∈ X.
Since the graph is bipartite, every vertex in C that belongs to X must be followed by a vertex that belongs to Y except for the last vertex — which is x₁ again. Thus, if we label the vertices in C according to which subset they belong to, C looks like this:
C = x₁, y₁, …, xᵢ, yᵢ, …, xₙ, yₙ, x₁.
Thus, C has 2n + 1 vertices, which implies it has 2n edges.
Now, for the sufficient condition, let’s prove the contrapositive claim:
If G is not bipartite, it must have an odd-length cycle.
(In the following, we assume that G is connected. Otherwise, the same arguments work for every connected component independently.)
To show why this is true, we will attempt to build a bi-partition of G and assume we fail; then show the reason must be that we found and odd cycle. First, note that for a graph to not be bipartite, it must have cycles, because trees are always bipartite!
To see why, just start at a random vertex, label it as blue (i.e., belonging to X), then label its neighbors as yellow (i.e., belonging to Y), and so on. Since there are no cycles in a tree, you will never find an edge that points to an already assigned vertex, because there is a single path to every vertex. So this partitioning will always succeed.
Now, let’s assume G has at least one cycle. What we’ll do is remove cycle edges until we have a tree and repeat the same labeling procedure. Then, we will add the missing edges back and check if we ever get a conflict.
Formally, we can say the following. Let T be a spanning tree of G. Bi-partition the vertices of G according to T. We already showed this always produces a valid partition. Now, add the edges of E(G) − E(T) one at a time, and let e = uv be the first edge that creates a conflict — i.e., the first edge that must go between vertices that had the same label according to T.
Since u and v have the same label in T, it follows that there is an even number of edges in the unique path between u and v. (This is because the way we label vertices in a tree is alternating, one blue, one red, and so on.) Thus, the edge uv closes the cycle, which now has an odd number of edges. ◼
Now that we have a surefire way of determining whether any graph is bipartite, let’s go back to the problem of finding matchings in these types of graphs.
Matching in bipartite graphs
Since bipartite graphs are graphs (duh), all our previous results work, so the condition that a matching is maximum if and only if there is no augmenting path is still true. However, what we are truly interested in, going back to our original motivational problem of the book club, is whether we can guarantee that all books will be assigned to someone.
In graph theory, a matching that touches all edges of one partition, say, X, is just called a matching of X, but to avoid confusion we will call it a full matching of X.
Definition 5. In a bipartite graph G = (X ∪ Y, E), a matching M is called a full matching of X if for every vertex v ∈ X there is an edge uv ∈ M. If the matching is full for both X and Y, it is called a perfect matching.
(Note that a perfect matching implies that X and Y have the same size.)
We will close off this entry by studying when a bipartite graph contains a full matching. Like before, we will first derive a necessary condition and then see if we can make it sufficient.
The first thing to note is that a full matching of X implies there are at least as many vertices in Y, if not more. Why? Because every vertex in X is matched to a distinct vertex in Y. Furthermore, we can do the same reasoning with every subset of X. Let’s make this formal.
Definition 6: In a graph G, given a subset of vertices S ⊆ V(G), the neighborhood of S is denoted as N(S) and defined as the set of vertices u ∈ V(G) connected to any vertex v ∈ S, i.e., uv ∈ E.
The neighborhood, in bipartite graphs, formalizes the notion of “all vertices in Y that could match these subset of vertices in X“. With this definition, we can formulate our first necessary condition for finding a full matching.
Lemma 1. (Hall’s necessary condition) In a bipartite graph G = (X ∪ Y, E), if there is a full matching of X, then for every subset S ⊆ X we have |S| ≤ |N(S)|.
This condition already gives us a tool to reject the possibility of a full matching whenever we can find a subset of, say, 4 books that have collectively being read by less than 4 people. Intuitively, we can see why such a configuration would prevent us from finding any way to match all 4 books to distinct readers. Let’s sketch a proof of this idea.
Proof: We don’t need too much formality to see why this must be true. Just notice that, if there is a subset of vertices S with less neighbors than |S|, then necessarily some of the vertices in S would need to be matched to the same vertex in N(S).
(This argument is often called the pigeonhole principle. You can’t put n pigeons in less than n holes without having two pigeons share a hole.)
Since any possible matching that includes all vertices in S must match them to distinct vertices in N(S) — to be a valid matching — this means there can’t be a full matching of X, because at least one vertex in S won’t find an unmatched vertex in N(S). ◼
Knowing when a full match is impossible is nice, but can we turn this necessary condition into a sufficient one? Surprisingly, yes!
Theorem 3. (Hall) A bipartite graph G = (X ∪ Y, E) has is a full matching of X if and only if for every subset S ⊆ X we have |S| ≤ |N(S)|.
The necessary part is done. Proving the sufficient part of Hall’s theorem is a bit more involved than anything we’ve done so far, so we will not attempt to give a full proof, but a sketch of it. The intuitive idea is that we can always grow an incomplete matching — i.e., finding an augmenting path — if the neighborhoods of all subsets are large enough.
Proof: Let’s assume that the maximum matching M in a bipartite graph G (where |N(S)| ≥ |S| for all S ⊆ X) is not a full matching. Thus, there must some vertex v in X that is not M-matched. We will build a convenient set S in which we’ll find our augmenting path, and invoke a contradiction with the claim that M is maximum.
To do so, start with S = {v}, and move to Y via v’s adjacent vertices. They all have to be M-matched, otherwise it would be trivial to match v and our matching wouldn’t be maximum. Thus, from all these v-adjacent vertices move back to X via the matching, add all those to S. Then, keep doing the same until no more vertices in X can be added to S.
At this point, we have a set S for which all vertices except one (v) are M-matched with corresponding vertices in N(S). But since |N(S) |≥ |S| and we have one unmatched vertex in S, then there has to be at least one unmatched vertex u in N(S), otherwise, |N(S)| would equal |S| − 1. Now notice that the way constructed S means that all paths in it are M-alternating, and that’s how we build our augmenting path! ◼
And voilá, we have found a necessary and sufficient condition for a full matching in a bipartite graph.
Back to our book club problem, can we make it any better? Well, Hall’s theorem gives us not only proof of a sufficient condition but also an algorithm — albeit a rather terrible one — to turn any matching into a full matching if possible.
Let’s do it!
In this example, the set X that we want to match is our books, so beware because X and Y are inverted in this drawing with respect to our previous examples — but of course, this isn’t an issue, right?
We begin at our unmatched book, The Chronicles of Narnia, and move to its adjacent vertices (Bob and Tom). Then we return to the books list via matched edges and repeat, finding two more vertices (Mary and Sally). In this second iteration, we already find Mary as an unmatched vertex. We don’t need to continue searching; we can build an augmenting path and increase our matching, by changing Mary with Tom and assigning Tom the unmatched book. And then, we immediately know we’re done because all books have been matched.
This is a very illustrative example of the whole theme of this series, which is that many proofs in computational math are actually algorithms that one can use to solve problems. Oftentimes — like in this case — the algorithms are far from optimal in terms of performance, though. But still, it’s a superior form of knowledge: just knowing that a full matching is possible versus knowing how to find one in a concrete example.
Closing remarks
Formalizing the proofs for Hall’s theorem is a bit beyond the scope of this article, but it’s not that hard. All you have to do is, instead of writing the proof as an informal procedure (e.g., “move to Y until you can’t no further…”), directly define the end result, e.g., “let H be the induced subgraph of all vertices reachable by M-alternating paths from v“. However, doing this doesn’t add anything interesting to our discussion and only obscures the intuitions, so we left it out.
Since this series focuses on theory instead of algorithms, we will not explore matching any further. But rest assured, there are extremely efficient algorithms for finding maximum matchings in bipartite graphs. The most used involves building a flow network and applying a maximum flow procedure. (We will look at it in a future series focused on graph algorithms.)
Matching is such an important problem in logistics and scheduling problems in general, that is has received tremendous attention from researchers. We only barely scrapped the surface here, but I hope the intuitions we built in this article have been not only surprising but also satisfying for you.
Next up, we’ll be visiting old cities and counting bridges.
 | A guest post by
|