Perfect-Matching Decompositions
A matching uses edges with no shared endpoints. In a bipartite graph, a perfect matching pairs every vertex on one side with a vertex on the other. The useful feature of a regular bipartite graph is that the same degree count that balances its two sides also supplies Hall’s condition. Hall’s theorem then gives one perfect matching. Removing its edges lowers every degree by exactly one, so the argument can be repeated until no edges remain.
Here graphs are finite bipartite multigraphs: parallel edges are allowed, but loops are not. Distinct parallel edges are treated as distinct edge instances. If \(X,Y\) are the parts, every edge has one endpoint in \(X\) and one in \(Y\). The degree of a vertex counts incident edge instances with multiplicity.
Parallel edges do not give a matching extra choices of neighbors: the neighborhood \(N(S)\) of \(S\subseteq X\) is the set of vertices of \(Y\) joined to at least one vertex of \(S\). They do, however, count separately toward degrees and toward the edge partition.
Why Hall’s Condition Holds
Proof. Count edge instances by their endpoints in each part. Every edge has one endpoint in \(X\) and one in \(Y\), so counting from either side gives the total number of edges \(m\). Regularity gives \(m=d|X|\) and \(m=d|Y|\). Since \(d>0\), these equalities imply \(|X|=|Y|\).
Now take any \(S\subseteq X\). Exactly \(d|S|\) edge instances are incident with vertices in \(S\), and every one of them ends in \(N(S)\). The total number of edge incidences at vertices of \(N(S)\) is \(d|N(S)|\). These incidences include all the edge instances from \(S\) just counted, so \(d|S|\le d|N(S)|\). Dividing by \(d>0\) gives \(|S|\le |N(S)|\). Hall’s theorem supplies a matching saturating \(X\). Because \(|X|=|Y|\), this matching also saturates \(Y\): it uses \(|X|\) distinct vertices of \(Y\), which is all of \(Y\). Thus it is perfect. \(\square\)
The counting argument counts parallel edges as separate incidences. Hall’s condition, by contrast, counts distinct neighbors. Keeping those two counts separate is essential: the degree count proves the condition, and Hall’s theorem turns the condition into a matching.
The Decomposition Theorem
Proof. We use induction on the nonnegative integer \(d\), proving the statement for all finite bipartite multigraphs of each degree. If \(d=0\), every vertex has degree zero, so there are no edge instances. The empty family of matchings is the required decomposition.
Now let \(d\ge1\), and assume the theorem holds for degree \(d-1\). By the lemma, the graph has a perfect matching \(M\). Delete the edge instances of \(M\), keeping all vertices. Each vertex was incident with exactly one edge of \(M\), so its degree in the remaining bipartite multigraph is \(d-1\). By the induction hypothesis, the remaining edge instances partition into \(d-1\) perfect matchings. Those matchings together with \(M\) partition the original edge set into \(d\) perfect matchings: \(M\) is disjoint from the remaining edges, and the induction hypothesis partitions those remaining edges. This completes the induction. \(\square\)
The induction is on degree, not on the number of vertices. It does not remove vertices: removing a perfect matching preserves both parts and lowers the degree of every vertex uniformly. The case \(d=0\) also shows why isolated vertices cause no problem at the end of the process.
Worked Example: A 3-Regular Multigraph with Parallel Edges
Let \(X=\{a,b\}\), \(Y=\{x,y\}\), and take the edge instances \(E=\{ax_1,ax_2,ay_1,bx_1,by_1,by_2\}\). The subscripts distinguish parallel instances: \(ax_1\) and \(ax_2\) have the same endpoints, as do \(by_1\) and \(by_2\).
The degrees, counting instances, are \(\deg(a)=3\), \(\deg(b)=3\), \(\deg(x)=3\), and \(\deg(y)=3\). A decomposition is \(M_1=\{ax_1,by_1\}\), \(M_2=\{ax_2,by_2\}\), and \(M_3=\{ay_1,bx_1\}\). Each set has one edge incident with each of \(a,b,x,y\), so each is a perfect matching. The three sets are pairwise disjoint and together contain all six listed edge instances.
Check: the degrees on both sides give \(3\cdot2=6\) edge incidences per side, corresponding to the six edge instances. The decomposition contains \(2+2+2=6\) instances, and every listed instance occurs exactly once.
Worked Example: Decomposing \(K_{3,3}\)
Let \(X=\{a,b,c\}\), \(Y=\{x,y,z\}\), and let the edge set be all nine pairs \(E=\{ax,ay,az,bx,by,bz,cx,cy,cz\}\). This is a 3-regular bipartite graph. Define \(M_1=\{ax,by,cz\}\), \(M_2=\{ay,bz,cx\}\), and \(M_3=\{az,bx,cy\}\).
In each \(M_i\), every vertex of \(X\) appears once and every vertex of \(Y\) appears once, so each set is a perfect matching. Listing the edges by their first endpoint checks the partition: the edges at \(a\), namely \(ax,ay,az\), appear once each across \(M_1,M_2,M_3\); those at \(b\), namely \(bx,by,bz\), appear once each; and those at \(c\), namely \(cx,cy,cz\), appear once each.
Check: each matching has three edges, so the three matchings contain \(3+3+3=9\) edges, equal to the nine edges in \(E\). The list-by-endpoint check also confirms that none is repeated or omitted.
Worked Example: A Disconnected Regular Multigraph
Let \(X=\{a,b,c,d\}\), \(Y=\{x,y,z,w\}\), and let \(E=\{ax,ay,bx,by,cz,cw,dz,dw\}\). The graph consists of two components: one on \(\{a,b,x,y\}\), and one on \(\{c,d,z,w\}\). Every vertex has degree \(2\). Set \(M_1=\{ax,by,cz,dw\}\) and \(M_2=\{ay,bx,cw,dz\}\).
For \(M_1\), the endpoints are \(a,b,c,d\) on the \(X\)-side and \(x,y,z,w\) on the \(Y\)-side, each used once. The same is true for \(M_2\). Thus both are perfect matchings of the whole graph, not merely of one component. Their edge sets are disjoint, and listing the four edges from each component shows that together they contain every edge of \(E\).
Check: each matching has four edges, and \(4+4=8=|E|\). In each component, the two matchings use its four edges exactly once, so the decomposition also works component by component.
Common Pitfall: Counting Parallel Edges
In the first example, a mistaken degree calculation might treat \(ax_1\) and \(ax_2\) as one edge because they have the same endpoints. That would give \(\deg(a)=2\), counting only the neighbors \(x\) and \(y\). The correction is that degree counts incident edge instances: \(a\) is incident with \(ax_1,ax_2,ay_1\), so \(\deg(a)=3\). For Hall’s condition, however, \(N(\{a\})=\{x,y\}\) has size \(2\), not \(3\). The proof works precisely because it uses multiplicity for the degree count and distinct vertices for the neighborhood.
Another tempting but invalid shortcut is to find a matching that covers only one part of a disconnected graph and call it perfect. A perfect matching must cover every vertex in both parts. In the disconnected example, each component contributes edges to each matching, so all eight vertices are covered.
The decomposition gives a concrete way to organize the edges: each matching is a separate layer, and every vertex meets exactly one edge in each layer. The proof guarantees the layers exist even when the graph has parallel edges or multiple components. The degree-zero case is included, while for positive degree the equal sizes of the two parts follow from the same incidence count used to establish Hall’s condition.
Check Your Understanding
Use the theorem and its proof to answer these questions.
- Why does \(d|X|=d|Y|\) imply equal part sizes only when \(d>0\)?
- For \(S\subseteq X\), explain why the \(d|S|\) edge instances incident with \(S\) are included among the \(d|N(S)|\) incidences at \(N(S)\).
- In a 4-regular bipartite multigraph, what degree does each vertex have after one perfect matching is deleted?
- Why can a matching saturating \(X\) be concluded to saturate \(Y\) in the positive-degree regular case?
- In the first worked example, state \(|N(\{a\})|\) and \(\deg(a)\), and explain why these numbers differ.