Why Regularity Forces a Perfect Matching
A regular bipartite graph has the same number of edges incident with each vertex. That uniformity puts a strong restriction on how many vertices a subset of one part can reach: the subset sends out a fixed number of edge incidences, while its neighbors can receive only a bounded number of them. Counting these incidences gives Hall’s condition, and Hall’s theorem then supplies a matching that covers every vertex on that side.
All graphs in this tutorial are finite and simple. A graph is bipartite if its vertex set can be partitioned into two sets \(X\) and \(Y\) so that each edge has one endpoint in each set. We call \((X,Y)\) a bipartition. A graph is \(d\)-regular if every vertex has degree \(d\), where \(d\) is a nonnegative integer. For \(S\subseteq X\), its neighborhood \(N(S)\) is the set of vertices in \(Y\) adjacent to at least one vertex of \(S\).
Hall’s condition for the side \(X\) is the inequality \(|N(S)|\ge |S|\) for every subset \(S\subseteq X\). We use Hall’s theorem in its standard finite form: a bipartite graph with parts \(X,Y\) has a matching saturating \(X\) if and only if Hall’s condition holds for every \(S\subseteq X\). Hall’s theorem was proved in the earlier material on systems of distinct representatives and matchings.
The Edge-Counting Argument
Proof. If the graph has no vertices, the empty matching is perfect, so suppose \(V\ne\varnothing\). Let \((X,Y)\) be a bipartition. Since every vertex has degree \(d\), counting each edge at its endpoint in \(X\) gives \(|E|=d|X|\). Counting each edge at its endpoint in \(Y\) gives \(|E|=d|Y|\). As \(d>0\), these equalities imply \(|X|=|Y|\).
Now fix any \(S\subseteq X\). There are exactly \(d|S|\) edges with one endpoint in \(S\): each vertex in \(S\) is incident with \(d\) edges, and no edge is counted at two vertices of \(S\), since there are no edges within \(X\). All these edges end in \(N(S)\). Each vertex in \(N(S)\) has total degree \(d\), so at most \(d\) of these edges can end at any one such vertex. Consequently, \(d|S|\le d|N(S)|\). Dividing by \(d>0\) gives \(|S|\le |N(S)|\). This also holds when \(S=\varnothing\), since both sides are zero. Hall’s condition is therefore satisfied, so Hall’s theorem gives a matching saturating \(X\). That matching has \(|X|\) edges and hence saturates \(|X|\) distinct vertices of \(Y\). Since \(|X|=|Y|\), it saturates all of \(Y\) as well, making it a perfect matching. \(\square\)
The proof needs both parts of the counting argument. The edge count from a subset \(S\) proves Hall’s condition; the count over the entire graph proves that the two parts have equal size. A matching saturating \(X\) alone would not, in general, guarantee that every vertex in a larger part \(Y\) is matched.
Worked Examples
Worked Example: A Connected 2-Regular Bipartite Graph
Let \(G=(V,E)\) have parts \(X=\{a,b,c\}\) and \(Y=\{1,2,3\}\), with edge set \(E=\{a1,a2,b2,b3,c3,c1\}\). Verify regularity, apply the counting argument to a subset, and find a perfect matching.
The degrees are \(\deg(a)=2\), since \(a\) is incident with \(a1,a2\); \(\deg(b)=2\), from \(b2,b3\); and \(\deg(c)=2\), from \(c3,c1\). On the other side, \(\deg(1)=2\), from \(a1,c1\); \(\deg(2)=2\), from \(a2,b2\); and \(\deg(3)=2\), from \(b3,c3\). Thus every vertex has degree \(d=2\). There are six listed edges, and counting from either part gives \(2\cdot 3=6=|E|\), so the part sizes agree.
Take \(S=\{a,b\}\). Its neighborhood is \(N(S)=\{1,2,3\}\), because \(a\) is adjacent to \(1,2\) and \(b\) to \(2,3\). The number of edges from \(S\) is \(2\cdot 2=4\). Each of its three neighbors can receive at most two of these edges, so the capacity bound is \(2\cdot 3=6\). The inequality \(4\le6\) is consistent with Hall’s condition \(|S|=2\le3=|N(S)|\).
A perfect matching is \(M=\{a1,b2,c3\}\). Its edges are all in \(E\), and they use each of \(a,b,c,1,2,3\) exactly once. Hence \(M\) is a matching saturating both parts. As an independent size check, \(M\) has three edges, equal to \(|X|=|Y|=3\); no matching can have more than three edges because its edges use distinct vertices of \(X\).
Worked Example: The Complete Bipartite Graph \(K_{3,3}\)
Let \(G=K_{3,3}\), with parts \(X=\{a,b,c\}\) and \(Y=\{1,2,3\}\), and edge set \(E=\{a1,a2,a3,b1,b2,b3,c1,c2,c3\}\). Each vertex is adjacent to all three vertices in the other part, so every degree is \(3\). There are \(3\cdot3=9\) listed edges, matching the count \(3|X|=3\cdot3=9\) from \(X\) and \(3|Y|=3\cdot3=9\) from \(Y\).
For a nonempty subset \(S\subseteq X\), every vertex of \(Y\) is adjacent to each vertex of \(S\), so \(N(S)=Y\) and \(|N(S)|=3\). The possible nonempty subset sizes are \(|S|=1,2,3\); in each case \(|S|\le3=|N(S)|\). For \(S=\varnothing\), both sizes are zero. This checks Hall’s condition for every subset, classified by whether it is empty and by its size.
Choose \(M=\{a1,b2,c3\}\). These three edges occur in the specified edge set and have no shared endpoints, so they form a matching. The matching saturates all six vertices. As a check, any matching has at most three edges because \(X\) has only three vertices, while \(M\) has exactly three; therefore its size is as large as possible, and it is perfect.
Worked Example: A Disconnected 2-Regular Bipartite Graph
Let \(G\) have parts \(X=\{a,b,c,d\}\) and \(Y=\{1,2,3,4\}\), with edge set \(E=\{a1,a2,b1,b2,c3,c4,d3,d4\}\). The vertices \(a,b,1,2\) form one component and \(c,d,3,4\) form another. Each of the eight vertices is incident with exactly two listed edges, so \(G\) is 2-regular. Counting from \(X\) gives \(2\cdot4=8\) edges, which agrees with the eight edges in \(E\); counting from \(Y\) gives \(2\cdot4=8\) as well.
Consider \(S=\{a,b\}\). Then \(N(S)=\{1,2\}\). The four edges incident with \(S\) are \(a1,a2,b1,b2\), so their number is \(2\cdot2=4\). The two neighbors have combined capacity \(2\cdot2=4\), and \(|N(S)|=2=|S|\). This subset attains equality in Hall’s condition.
Take \(M=\{a1,b2,c3,d4\}\). Each listed edge belongs to \(E\), and no endpoint appears in two selected edges, so \(M\) is a matching. It contains four edges and uses all four vertices of each part. Its size is checked directly from the four selected edges; it is also the largest possible size because a matching can use each of the four vertices in \(X\) at most once. The two components are both covered, showing that connectedness is not required.
What the Hypotheses Do
The degree \(d\) must be positive for the division in the proof. The empty graph is already handled separately, but a nonempty 0-regular graph need not have a perfect matching: for example, take \(V=\{a,b\}\), \(E=\varnothing\), \(X=\{a\}\), and \(Y=\{b\}\). Each degree is zero, but no edge can be chosen to match either vertex. Regularity alone is not enough without the condition \(d>0\).
Bipartiteness is also essential to this argument. It ensures that every edge from \(S\subseteq X\) ends in \(N(S)\), and that each such edge is counted once when degrees are summed over \(X\). The theorem is a sufficient condition, not a claim that every bipartite graph with a perfect matching must be regular. For instance, the graph with \(X=\{a,b\}\), \(Y=\{1,2\}\), and \(E=\{a1,b1,b2\}\) has the perfect matching \(\{a1,b2\}\), although its vertex degrees are not all equal.
In applications, the proof’s key move is local: inspect an arbitrary subset \(S\) of one part, count the edge incidences leaving it, and bound how many can arrive at each neighbor. Because the same positive degree \(d\) appears on both sides of the inequality, it cancels and yields exactly the size comparison Hall’s theorem requires.
Common Pitfall
A frequent error is to forget that a neighbor can receive as many as \(d\) edges from \(S\), rather than just one. In the first example, \(S=\{a,b\}\) has four incident edges but only three neighbors. The incorrect inequality \(d|S|\le |N(S)|\) would say \(4\le3\), which is false. The correct count is \(d|S|\le d|N(S)|\): here it says \(4\le6\), and after dividing by \(d=2\), it gives \(2\le3\), the required Hall inequality. The capacity factor \(d\) on the right is essential.
Check Your Understanding
Use edge counts and the theorem to answer the following.
- In a finite 4-regular bipartite graph with parts \(X,Y\), explain why \(|X|=|Y|\).
- For \(S\subseteq X\), explain why the number of edges from \(S\) to \(N(S)\) is \(d|S|\) and why it is at most \(d|N(S)|\).
- Why does a matching saturating \(X\) become perfect when the graph is \(d\)-regular with \(d>0\)?
- Give a nonempty 0-regular bipartite graph with no perfect matching, and identify which step of the proof cannot be used.
- In the disconnected example, verify directly that the edge set \(\{a2,b1,c4,d3\}\) is also a perfect matching.