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.
Here’s a condition for matchings in a bipartite graph.
Every regular bipartite graph contains a perfect matching
Let be a regular bipartite graph, i.e. every vertex has degree with more than three vertices. Then 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 ), consider .
Let then, we know that as every vertex in is incident to precisely edges (as it is a -regular graph), .
To apply Hall’s condition we want to consider (the neighbourhood of ). Specifically, we would like to prove that
which we can do by considering that every edge incident to is also incident to (by definition), so the number of edges incident to cannot be greater than the total number of edges incident to .
Or, in mathematical language
thus there exists a matching of size . By symmetry, the proof also allows us to conclude that there is a matching of size . This means that we can match every vertex in to one in (and vice versa), so there exists a perfect matching. Note that this also means that in such a graph , 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).