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. This gives us another special type of graph.
A graph $G = (V,E)$ is bipartite if $V$ is the disjoint union of two sets $V_1$ and $V_2$ such that all edges in $E$ connect a vertex in $V_1$ with a vertex in $V_2$. We say that $(V_1, V_2)$ is a bipartition of $V$.
We get the following characterization of bipartite graphs for free from the definition of 2-colourability.
A graph $G$ is bipartite if it is 2-colourable.
Similar to the idea of complete graphs, we can define complete bipartite graphs.
The complete bipartite graph on $m$ and $n$ vertices is the graph $K_{m,n} = (V,E)$, where $(V_m,V_n)$ is a bipartition of $V$ with $|V_m| = m$ and $|V_n| = n$, and $$E = \{(u,v) \mid u \in V_m, v \in V_n \}.$$
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 maximal matching is a matching that cannot be made larger; in other words, every edge in $E \setminus M$ is incident to a vertex matched in $M$. A maximum matching is a matching with the maximum number of edges. A matching $M$ in a bipartite graph $G = (V,E)$ with bipartition $(V_1, V_2)$ is a complete matching from $V_1$ to $V_2$ if every vertex in $V_1$ is matched in $M$.
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.
The following result gives us a necessary and sufficient condition for a bipartite graph to have a complete matching and is due to Philip Hall, who was a British group theorist and worked at Bletchley Park during the Second World War.
Let $G = (V,E)$ be a bipartite graph with bipartition $(V_1,V_2)$. Then $G$ has a complete matching from $V_1$ to $V_2$ if and only if $|N(A)| \geq |A|$ for all subsets $A \subseteq V_1$.
First, consider the only if direction. Here, we suppose there is a complete matching $M$ from $V_1$ to $V_2$. Consider a subset $A \subseteq V_1$. Since $M$ is a complete matching, we know that there is at least one edge (the one in $M$) for each vertex $v \in V_1$. This means there is at least one neighbour in $V_2$ for each vertex $v \in V_1$. Therefore, $|N(A)| \geq |A|$.
The if direction is proved by strong induction on $|V_1|$.
Base case. We have $|V_1| = 1$, so $V_1 = \{v\}$. Since $|N(V_1)| \geq |V_1|$, there exists an edge $(v,u)$ with $u \in V_2$. The complete matching consists of this edge.
Inductive case. Let $k \gt 1$ and assume for a graph $G = (V,E)$ with bipartition $(V_1,V_2)$ that if $|V_1| = j \leq k$, then there is a complete matching from $V_1$ to $V_2$ if $|N(A)| \geq |A|$ for all subsets $A \subseteq V_1$.
Consider a graph $G = (V,E)$ with bipartition $(V_1,V_2)$ and $|V_1| = k+1$. There are two cases to consider.
In the first case, we have that for all subsets $A \subseteq V_1$ of size $j$ with $1 \leq j \leq k$, $|N(A)| \gt |A| = j$. In this case, we choose a vertex $v \in V_1$ and a vertex $u \in V_2$ that is adjacent to $v$. Consider the subgraph $H$ that results when we delete $v$ and $u$ and all edges incident to them. This graph has a bipartition $(V_1 \setminus \{v\}, V_2 \setminus \{u\})$. Since $|V_1 \setminus \{v\}| = k$, by the inductive hypothesis, $H$ has a complete matching $M$. Then we can construct a complete matching $M$ for $G$ by taking $M = M \cup \{(v,u)\}$.
In the second case, there exists a subset $A \subseteq V_1$ of size $j$ with $1 \leq j \leq k$ such that $|N(A)| = |A| = j$. Let $B = N(A)$. By the inductive hypothesis, there is a complete matching $M_1$ from $A$ to $B$. Now consider the subgraph $H$ that results from deleting $A$,$B$, and all edges incident to them.
The graph $H$ has a bipartition $(V_1 \setminus A, V_2 \setminus B)$. We claim that for all subsets $S \subseteq V_1 \setminus A$, we have $|N(S)| \geq |S|$. Assume to the contrary. Then there exists a subset $T \subseteq V_1 \setminus A$ of size $t$ with $1 \leq t \leq k+1-j$ such that $|N(T)| \lt |T| = t$. But then this implies that $|N(A \cup T)| \lt |A \cup T|$, which contradicts our original assumption.
Therefore, $|N(S)| \geq |S|$ for all subsets $S \subseteq V_1 \setminus A$. Since $|V_1 \setminus A| \leq k$, there exists a perfect matching $M_2$ from $V_1 \setminus A$ to $V_2 \setminus B$. Then, we can construct a complete matching $M$ for $G$ by taking $M = M_1 \cup M_2$.
Thus, in both cases, we have constructed a complete matching.
Obviously, not every bipartite graph will contain a complete matching. However, perhaps we would like to try to find a maximum matching. But if we just go and choose a matching, we may end up with a maximal matching. Can we be sure that we have a maximum matching and not just a maximal matching? 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 Example 17.21:
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 $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\}$. Note that $M'$ is a matching of $G$ and was constructed by removing $k$ edges from $M$ and adding $k+1$ edges. Thus, $|M'| = |M| + 1 \gt |M|$. So $M$ was not a maximum matching.
In fact, this is one direction for Berge's lemma, 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.
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!
However, this issue with our algorithm is only a problem because the cycle that's giving us the problem has odd length. Luckily, this is not a problem for bipartite graphs.
A graph $G$ is bipartite if and only if $G$ does not contain a cycle of odd length.
First, we show the only if direction. Suppose $G$ is bipartite and consider a cycle in $G$. Then traversing an edge on this cycle means alternating between the two sets of the bipartition. Since we must return the starting vertex, we must end up in the same set of the bipartition that we started in, which means that the cycle must have an even number of edges.
Now, we consider the if direction and suppose that $G$ does not contain a cycle of odd length. We assume without loss of generality that $G$ is connected, since $G$ is bipartite if and only if all of its connected components are bipartite.
Choose a vertex $v \in V$. We define two sets, \begin{align*} V_1 &= \{u \in V \mid \text{there exists an odd length path between $u$ and $v$}\}, \\ V_2 &= \{u \in V \mid \text{there exists an even length path between $u$ and $v$}\}. \\ \end{align*} We observe that $V_1 \cup V_2 = V$, since $G$ is connected, and so there must be a path between $v$ and each vertex in $G$.
We claim that $V_1 \cap V_2 = \emptyset$. Suppose otherwise and that there exists a vertex $u \in V_1 \cap V_2$. Then there exists a path of even length from $u$ to $v$ and a path of odd length from $v$ to $u$. These two paths together form a cycle of odd length, which contradicts our assumption that no such cycles exist.
Since $V_1$ and $V_2$ are disjoint and cover $V$, they form a bipartition of $V$, and therefore, $G$ is bipartite.
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. Jack Edmonds was a faculty member at the University of Waterloo, where I did my undergrad, and he was a member of the Department of Combinatorics and Optimization. A fun fact about Edmonds is that he has a big rock on his front lawn that has $\mathrm{NP} \neq \mathrm{NP} \cap \mathrm{coNP} = \mathrm{P}$ inscribed on it.
Nowadays, the maximum matching problem is usually solved by using the Ford-Fulkerson maximum flow algorithm, which has a running time of $O(|V||E|)$. This is for all graphs; if one restricts consideration to bipartite graphs, we can use a faster algorithm due to Hopcroft and Karp, which has a running time of $O(\sqrt{|V|}|E|)$.