More Discrete Mathematicsvia Graph Theory

Section1.6Matching in Bipartite Graphs

In any matching is a subset \(M\) of the edges for which no two edges of \(M\) are incident to a common vertex. If every vertex belongs to exactly one of the edges, we say the matching is perfect. Our goal is to discover some criterion for when a bipartite graph has a prefect matching.

Suppose you have a bipartite graph \(G\text{.}\) This will consist of two sets of vertices \(A\) and \(B\) with some edges connecting some vertices of \(A\) to some vertices in \(B\) (but of course, no edges between two vertices both in \(A\) or both in \(B\)). A matching of \(G\) is a set of independent edges, meaning no two edges in the set are adjacent. If every vertex in \(G\) is incident to exactly one edge in the matching, we call the matching perfect. If a bipartite graph has a perfect matching, then \(\card{A} = \card{B}\text{,}\) but in general, we could have a matching of \(A\), which will mean that every vertex in \(A\) is incident to an edge in the matching.

Some context might make this easier to understand. Think of the vertices in \(A\) as representing students in a class, and the vertices in \(B\) as representing presentation topics. We put an edge from a vertex \(a \in A\) to a vertex \(b \in B\) if student \(a\) would like to present on topic \(b\text{.}\) Of course, some students would want to present on more than one topic, so their vertex would have degree greater than 1. As the teacher, you want to assign each student their own unique topic. Thus you want to find a matching of \(A\text{:}\) you pick some subset of the edges so that each student gets matched up with exactly one topic, and no topic gets matched to two students.⁶The standard example for matchings used to be the marriage problem in which \(A\) consisted of the men in the town, \(B\) the women, and an edge represented a marriage that was agreeable to both parties. A matching then represented a way for the town elders to marry off everyone in the town, no polygamy allowed.

Activity54

Does the graph below contain a perfect matching? If so, find one.

The question is: when does a bipartite graph contain a matching of \(A\text{?}\) To begin to answer this question, consider what could prevent the graph from containing a matching. This will not necessarily tell us a condition when the graph does have a matching, but at least it is a start.

Activity56

Find a matching of the bipartite graphs below or explain why no matching exists.

One way \(G\) could not have a matching is if there is a vertex in \(A\) not adjacent to any vertex in \(B\) (so having degree 0). What else? What if two students both like the same one topic, and no others? Then after assigning that one topic to the first student, there is nothing left for the second student to like, so it is very much as if the second student has degree 0. Or what if three students like only two topics between them. Again, after assigning one student a topic, we reduce this down to the previous case of two students liking only one topic. We can continue this way with more and more students.

It should be clear at this point that if there is every a group of \(n\) students who as a group like \(n-1\) or fewer topics, then no matching is possible. This is true for any value of \(n\text{,}\) and any group of \(n\) students.

To make this more graph-theoretic, say you have a set \(S \subseteq A\) of vertices. Define \(N(S)\) to be the set of all the neighbors of vertices in \(S\text{.}\) That is, \(N(S)\) contains all the vertices (in \(B\)) which are adjacent to at least one of the vertices in \(S\text{.}\) (In the student/topic graph, \(N(S)\) is the set of topics liked by the students of \(S\text{.}\)) Our discussion above can be summarized as follows:

Is the converse true? Suppose \(G\) satisfies the matching condition \(|N(S)| \ge |S|\) for all \(S \subseteq A\) (every set of vertices has at least as many neighbors than vertices in the set). Does that mean that there is a matching? Surprisingly, yes. The obvious necessary condition is also sufficient.⁷This happens often in graph theory. If you can avoid the obvious counterexamples, you often get what you want. This is a theorem first proved by Philip Hall in 1935.⁸There is also an infinite version of the theorem which was proved by the unrelated Marshal Hall, Jr.

There are a few different proofs for this theorem; we will consider one that gives us practice thinking about paths in graphs.

Activity58

Every bipartite graph (with at least one edge) has a matching, even if it might not be perfect. Thus we can look for the largest matching in a graph. If that largest matching includes all the vertices, we have a perfect matching.

Your “friend” claims that she has found the largest matching for the graph below (her matching is in bold). She explains that no other edge can be added, because all the edges not used in her partial matching are connected to matched vertices. Is she correct?

Activity59

One way you might check to see whether a partial matching is maximal is to construct an alternating path. This is a path whose adjacent edges alternate between edges in the matching and edges not in the matching (no edge can be used more than once, since this is a path). If an alternating path starts and stops with vertices that are not matched, (that is, these vertices are not incident to any edge in the matching) then the path is called an augmenting path.

(a)

Find the largest possible alternating path for the matching of your friend's graph. Is it an augmenting path? How would this help you find a larger matching?

(b)

Find the largest possible alternating path for the matching below. Are there any augmenting paths? Is the matching the largest one that exists in the graph?

If a graph does not have a perfect matching, then any of its maximal matchings must leave a vertex unmatched. In particular, there cannot be an augmenting path starting at such a vertex (otherwise the maximal matching would not be maximal). Thus to prove Theorem 1.6.2, it would be sufficient to prove that the matching condition guarantees that every non-perfect matching has an augmenting path.

In addition to its application to marriage and student presentation topics, matchings have applications all over the place. We conclude with one such example.