25.3 Matchings in graphs

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

todo!

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

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

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).