Decomposing Regular Bipartite Graphs Into Matchings

From One Perfect Matching to a Decomposition

A perfect matching pairs every vertex with exactly one adjacent vertex. In a regular bipartite graph, Hall’s theorem gives a way to find one such pairing: the equal degrees ensure that every subset of one part has enough neighbors. Removing the edges of that matching leaves another regular bipartite graph, now of degree one less. Repeating this process decomposes all the edges into perfect matchings.

There is an important hypothesis: the degree must be positive when the graph has vertices. A nonempty 0-regular graph has isolated vertices, so it has no perfect matching. We will state the result to cover the empty graph as well, using the convention that a matching is perfect if it covers every vertex, which is vacuously true when there are no vertices.

A bipartite graph \(G=(V,E)\) has a vertex partition \(V=X\cup Y\), with \(X\cap Y=\varnothing\), such that every edge has one endpoint in \(X\) and one in \(Y\). It is \(d\)-regular if every vertex has degree \(d\). All graphs here are finite and simple.

Why a Positive-Regular Bipartite Graph Has a Perfect Matching

We use Hall’s theorem in its finite bipartite form: a bipartite graph with parts \(X,Y\), where \(|X|=|Y|\), has a perfect matching if and only if \(|N(S)|\ge |S|\) for every \(S\subseteq X\). Here \(N(S)\) is the set of vertices of \(Y\) adjacent to at least one vertex of \(S\). Hall’s theorem is established in the earlier material on Hall’s marriage theorem.

Proof. Write the bipartition as \(X,Y\). Counting edges by their endpoints in \(X\) gives \(|E|=d|X|\), because each vertex of \(X\) has degree \(d\) and each edge has exactly one endpoint in \(X\). Counting by endpoints in \(Y\) gives \(|E|=d|Y|\). Since \(d\ge1\), these equalities imply \(|X|=|Y|\).

Now let \(S\subseteq X\). Every edge incident with a vertex of \(S\) ends at a vertex of \(N(S)\), so exactly \(d|S|\) edges have one endpoint in \(S\). Each vertex of \(N(S)\) has total degree \(d\), and thus can be incident with at most \(d\) of those edges. Consequently, \(d|S|\le d|N(S)|\). Dividing by the positive integer \(d\) gives \(|S|\le |N(S)|\). This also holds for \(S=\varnothing\), since both sides are zero. Hall’s theorem now gives a perfect matching. If \(V=\varnothing\), the empty matching is perfect by the stated convention. \(\square\)

The degree assumption is doing real work in this argument. In particular, dividing by \(d\) would not be valid at \(d=0\); more importantly, a nonempty graph of degree zero cannot have a perfect matching.

The Decomposition Theorem

Proof. We prove the assertion for nonempty graphs by induction on \(d\). For \(d=1\), every vertex is incident with exactly one edge. The set \(E(G)\) is therefore a matching, and it covers every vertex. It is one perfect matching and is the required decomposition.

Now suppose \(d\ge2\), and assume the assertion holds for degree \(d-1\). By the lemma, \(G\) has a perfect matching \(M_1\). Form \(G_1=(V,E\setminus M_1)\): remove the matching’s edges but keep all vertices. Each vertex was incident with exactly one edge of \(M_1\), so its degree in \(G_1\) is \(d-1\). The graph \(G_1\) is still bipartite with parts \(X,Y\), and it is finite and simple. The induction hypothesis therefore decomposes \(E(G_1)\) into \(d-1\) pairwise edge-disjoint perfect matchings \(M_2,\ldots,M_d\). None uses an edge of \(M_1\), because those edges were removed. Their union with \(M_1\) is all of \(E(G)\), so \(M_1,\ldots,M_d\) give the required decomposition.

For the empty graph, its edge set is empty. Taking \(d\) copies of the empty matching gives \(d\) perfect matchings under the vacuous-covering convention, and their union is the empty edge set. This handles that case too. \(\square\)

The proof is constructive in the following sense: at each stage, find a perfect matching in the current regular bipartite graph, record it, and delete only its edges. When the degree reaches zero, no edges remain. The proof guarantees that a suitable matching exists at every positive-degree stage.

Why the Removal Step Matters

To keep the graph regular, remove matching edges while retaining all vertices. A perfect matching removes exactly one incident edge at each vertex, so every degree falls by exactly one. Deleting the matched vertices instead would leave a smaller graph, not the same vertex set with degree \(d-1\); that is not the induction step used in the proof.

The theorem gives more than a way to cover vertices: it partitions every edge into layers, each layer a perfect matching. Since the graph is \(d\)-regular, the decomposition has exactly \(d\) matchings. For any vertex, one incident edge belongs to each matching, accounting for its \(d\) incident edges.

Common pitfall: forgetting the positive-degree condition. Consider the graph with \(V=\{a\}\) and \(E=\varnothing\). It is 0-regular, but it has no perfect matching: the only possible matching is empty, and it does not cover \(a\). Hall’s condition also fails for \(S=\{a\}\), since \(N(S)=\varnothing\) gives \(|N(S)|=0<1=|S|\). Thus the unqualified claim that every regular bipartite graph has a perfect matching is false. The theorem applies to graphs with \(d\ge1\); the empty graph is a separate vacuous case, while nonempty 0-regular graphs are excluded.