Recall that showing a graph is 2-colourable amounted to dividing the vertices up into two sets (or a partition) so that all of the edges of the graph only travel between these two sets. Such a graph is a bipartite graph. Bipartite graphs come up naturally in a lot of applications because a bipartite graph models relationships between two groups of things: job applicants and potential employers, PhD students and PhD advisors, pigeons and pigeonholes, etc. In many of these applications, we would like to assign or match an object from the first set with an object from the second. This leads to the following notion.
A matching in a graph $G = (V,E)$ is a subset of edges $M \subseteq E$ such that no two edges in $E$ share the same incident vertex. A vertex that is incident to an edge in a matching $M$ is matched in $M$; otherwise, it is unmatched.
A matching $M$ is said to be
The above definitions distinguish between maximal and maximum matchings. Just because you have a matching that can't be expanded doesn't mean that you necessarily have the largest possible matching!
Consider the following graph and the highlighted matchings.
On the left, we have a maximal matching, since no edges can be added to the matching without violating the matching condition. However, this graph can exhibit a larger matching, which we have on the right. Since every vertex on the bottom is matched, this is a complete matching, and therefore, it is also a maximum matching. However, other maximum matchings exist for this graph.
This matching also happens to be complete for one side of the bipartition. We would obviously like to be in this case whenever possible—obviously when both partitions are the same size, that would be great, but if not, then we would like this even just for the smaller side.
When might this not work? Let's say we're matching students to internships. If we look at some subset of students, say four or five of them, and they're only interested in two or three positions, then there's no way that they'll all get a position. So we can't find a complete matching for students.
First, let's formally define the set of vertices adjacent to a given vertex. Such vertices are neighbours, so we will call the set of neighbours a neighbourhood.
Let $G = (V,E)$ be a graph. The neighbourhood of a vertex $v \in V$ is the set of neighbours of $v$, \[N(v) = \{u \in V \mid (u,v) \in E\}.\] We can extend this definition to sets of vertices $A \subseteq V$ by \[N(A) = \bigcup_{v \in A} N(v).\]
Then it turns out the example we described is necessary and sufficient for a complete matching if we do this check for all subsets of vertices. This is Hall's matching condition.
Let $G = (V,E)$ be a bipartite graph with bipartition $(V_1, V_2)$. Then $G$ has a complete matching for $V_1$ if and only if $|N(A)| \geq |A|$ for all subsets $A \subseteq V_1$.
The proof of this is quite lengthy and it proceeds by strong induction. You can find it in the textbook.
Now, whether or not we have a complete matching, we would still like to try to find a maximum matching in our graph. One way to do this is greedily: just choose edges until we get a maximal matching. Such a matching might not be maximum, so we would like a way to figure out if, when we find ourselves with a maximal matching, whether there's a way to get a better matching or if such a matching exists. We will make use of the following idea.
Let $G$ be a graph with a matching $M$. An augmenting path for $M$ is a path $v_0 v_1 \cdots v_k$ such that $v_0$ and $v_k$ are unmatched in $M$ (i.e. $v_0, v_k$ do not belong to any matched edges) and the edges of the path alternate between edges in $M$ and edges not in $M$.
Let's have a look at what an augmenting path looks like.
Consider again our example:
We can see on the left, where we have a maximal but not maximum matching, there are many augmenting paths, while there are no such paths on the right. Now, observe that we can choose an augmenting path in the left-hand matching and if we flip all the edges in and out of the matching, we end up with the right-hand matching. This gives us a possible algorithm: start with an unmatched vertex and construct a matching iteratively by finding augmenting paths and flipping them.
Let $G = (V,E)$ be a graph with a matching $M$. If $G$ has an $M$-augmenting path, then $M$ is not a maximum matching.
First, we note that an $M$-augmenting path must be odd. Otherwise, the edges on the end can't both be outside of the matching. So suppose $G$ contains an $M$-augmenting path, denoted as a sequence of edges $e_1 e_2 \cdots e_{2k+1}$. By definition, $e_2, e_4, \dots, e_{2k} \in M$ and $e_1, e_3, \dots e_{2k+1} \not \in M$.
We define the matching $M' = (M \setminus \{e_{2i} \mid 1 \leq i \leq k\}) \cup \{e_{2i+1} \mid 0 \leq i \leq k\}$. In other words, $M'$ is a matching of $G$ that is constructed by removing $k$ edges from $M$ that were on our path and adding the other $k+1$ edges on our path. Thus, $|M'| = |M| + 1 \gt |M|$. So $M$ was not a maximum matching.
In fact, this is one direction for Berge's lemma, due to Claude Berge in 1957, which says that this condition is necessary and sufficient.
Let $G = (V,E)$ be a graph with a matching $M$. Then $M$ is a maximum matching if and only if there is no $M$-augmenting path.
We get an algorithm from this result:
However, while this is true for any matching, simply applying this method as an algorithm runs into one possible complication. Consider the following graph and matching.
Observe that if we attempt to find our augmenting path by starting from the leftmost vertex, we could end up getting stuck, depending on which way we travel on the cycle.
Now, you might say, hold on, this graph is not bipartite! And that's true, this is not a bipartite graph. But, if we look carefully at the definition of matchings and the statement of Berge's lemma, we'll find that neither of these actually depends on the fact that $G$ is bipartite! Luckily, this issue with our algorithm is only a problem for graphs that are not bipartite. Why? The problem arises when the graph contains and odd cycle and...
A graph $G$ is bipartite if and only if $G$ does not contain a cycle of odd length.
So for bipartite graphs, the algorithm that we've described works perfectly fine. But what about for general graphs? It takes a bit more work, but the same idea works once you can figure out how to deal with odd cycles. This result is due to Jack Edmonds in 1965, who gave the first efficient algorithm for computing maximum matchings in general graphs, and which contributed to the idea of "efficient" algorithms as those with polynomial running times.