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.


Every regular bipartite graph contains a perfect matching

Theorem 25.3.1

Let G=(AB,E)G=(A\cup B,E) be a regular bipartite graph, i.e. every vertex has degree kk with more than three vertices. Then GG 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 BB), consider SAS\subseteq A.

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

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


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

Or, in mathematical language

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

thus there exists a matching of size |A||A|. By symmetry, the proof also allows us to conclude that there is a matching of size |B||B|. This means that we can match every vertex in BB to one in AA (and vice versa), so there exists a perfect matching. Note that this also means that in such a graph |A|=|B||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).