# 25.3 Matchings in graphs

author’s reminder: as with the rest of this document, I am still writing it!

## 25.3.1 Bipartite matchings

Sometimes in life we would like to pair things together. For example, medicine students to hospital placements, etc.

### Hall’s condition

Here’s a condition for matchings in a bipartite graph.

todo!

### Every regular bipartite graph contains a perfect matching

###### Theorem 25.3.1

Let $G=(A\cup B,E)$ be a regular bipartite graph, i.e. every vertex has degree $k$ with more than three vertices. Then $G$ contains a perfect matching.

To prove this, we can show that Hall’s condition applies for such a graph. Without loss of generality (i.e. the argument will apply just as well to $B$), consider $S\subseteq A$.

Let $t:=\text{\# edges incident to A, i.e. edges with one edge in A}$ then, we know that as every vertex $v$ in $A$ is incident to precisely $k$ edges (as it is a $k$-regular graph), $t=k|S|$.

To apply Hall’s condition we want to consider $\Gamma(S)$ (the neighbourhood of $S$). Specifically, we would like to prove that

$|S|\leq|N(S)|$

which we can do by considering that every edge incident to $S$ is also incident to $N(S)$ (by definition), so the number of edges incident to $S$ cannot be greater than the total number of edges incident to $N(S)$.

Or, in mathematical language

$t\leq k|N(S)|\implies k|S|\leq|N(S)|\implies|S|\leq|N(S)|$

thus there exists a matching of size $|A|$. By symmetry, the proof also allows us to conclude that there is a matching of size $|B|$. This means that we can match every vertex in $B$ to one in $A$ (and vice versa), so there exists a perfect matching. Note that this also means that in such a graph $|A|=|B|$, as our perfect matching is effectively a bijective function (and if we have a bijective function between two sets they must be the same size).