In this post we go over some basic decomposition results in regular graphs, such as 1-factorization and 2-factorization, in both directed and undirected cases. These are useful when e.g. we want to represent a graph as some group action (a so-called Schreier graph); however, I haven't been able to find some of them properly written up on the internet.

1. Terminology and overview

Important note: in this post, a `graph' means an undirected graph which potentially has multiple edges and loops unless otherwise specified, a `simple graph' means a graph without multiple edges or loops, and a `digraph' means what it usually means: a directed graph which allows multiple edges and directed loops.

A $ k$-factor in a graph is a $ k$-regular subgraph on the same vertex set; analogously, a $ k$-factor in a digraph is a $ k$-regular subdigraph on the same vertex set.

We will mostly look at 1-factorization and 2-factorization. Clearly, if a graph can be 1-factored, it is regular and has an even number of vertices, but the converse doesn't hold; as usual, one counterexample is the Petersen graph. However, it does hold for bipartite regular graphs, as we'll see.

Similarly, a 2-factorable graph must be regular of even degree; however, in this case, the reverse implication works as well!

Finally, if we consider regular digraphs, they become 1-factorable again, though a 1-factor in a digraph is a union of cycles, not a matching.

2. 1-factors in (undirected) graphs

In the case of 1-factors, we need to prohibit loops in our graphs, because there's no way for a loop to be part of any 1-factor.

There are two easy cases: complete and bipartite graphs. A first easy observation is that

Proposition 1.

$ K_{2k}$ is 1-factorable.

Proof 1.

There's a nice geometric way to think about that. Let $ n=2k$ and consider the vertices of a regular $ 2k-1$-gon together with its center. Then the $ i$-th matching, for $ 1\leq i\leq 2k-1$, is formed by the segment joining the center with the $ i$-th vertex of the $ 2k-1$-gon, and all diagonals perpendicular to this segment. Easy breezy beautiful!

Next, the following is a well-known result:

Proposition 2.

A $ d$-regular bipartite graph $ G=(L,R)$ can be partitioned into $ d$ perfect matchings.

Proof 2.

It suffices to show that we can find a single perfect matching in $ G$, because removing it leaves us with a $ d-1$-regular bipartite graph.

We do it by Hall's theorem. Letting $ N_v = \left\{ u\in R \ \big| \ (v,u)\in E(G)\right\} $ be the neighborhood of $ v$, we want to find a system of distinct representatives for the family $ \{N_v\}_{v\in L}$, and for this it suffices to show that \begin{align*} \left| \displaystyle\bigcup_{v\in A}^{} N_v \right|\geq \left| A \right| \end{align*} There are $ d \left| A \right|$ edges between $ A$ and $ \displaystyle\bigcup_{v\in A}^{} N_v$, and since every $ u\in \displaystyle\bigcup_{v\in A}^{} N_v$ can accommodate at most $ d$ edges, the inequality follows and we're done.

Coming back to non-bipartite regular graphs, there's more to the story. Observe that if a graph $ G$ on $ 2k$ vertices has degree $ 2k-2$, its complement is a $ 1$-regular graph, thus a perfect matching, and by renaming the vertices we can make it be one of the matchings of $ K_{2k}$ we constructed above; it follows that $ G$ is 1-factorable as well. Investigating further, it seems that the problem is easy when the degree is large, and more generally we have

A $ d$-regular simple graph on $ 2k$ vertices is 1-factorable if $ d\geq k$ for odd $ k$, or $ d\geq k-1$ for even $ k$.

It's easy to find 1-factors while the degree remains large, by using e.g. Dirac's theorem:

Theorem 3 (Dirac's theorem) .

Any connected graph on $ n$ vertices where every degree is $ \geq n/2$ contains a Hamiltonian cycle.

Thus we can pick out a Hamiltonian cycle and then take alternating edges in the cycle to form two 1-factors. However, the best result towards the 1-factorization conjecture that we have is the following theorem due to Chetwynd and Hilton [CaH85]

Theorem 4.

A $ \geq 12k/7$-regular simple graph on $ 2k$ vertices is 1-factorable.

3. Cycle decompositions for regular graphs and digraphs

Next up, we show the fortunate equivalence of 2-factoring and even degree:

Theorem 5 (Petersen, 1891) .

A graph $ G$ is 2-factorable iff it is $ 2k$-regular.

The only if direction is trivial, but for the if direction it turns out that for somewhat technical reasons it is convenient to consider the problem on directed graphs first, and then reduce the undirected case to the directed case.

Indeed, if we apply the argument from 1-factorization of bipartite graphs to this case, we would naively hope that a system of distinct representatives for the sets of neighborhoods corresponds to a 2-factor, as it gives a permutation $ \pi$ on the vertex set such that $ (v,\pi(v))$ is an edge for all $ v$, and this permutation has some cycle decomposition. However, 2-cycles in this permutation break our 2-factors; i.e., we might get that the representative of $ u$ is $ v$ and the representative of $ v$ is $ u$, for some two distinct vertices $ u,v$ in the graph. To fix this, we make the following two moves:

Proposition 6.

Any $ k$-regular digraph $ G$ is 1-factorable.

Proof 3.

This is essentially the same application of Hall's theorem as in 1-factoring bipartite graphs. As before, with $ N_v = \left\{ u\in V(G) : v\to u\in E(G)\right\} $ we have that a system of distinct representatives for $ \{N_v\}_{v\in V(G)}$ gives a 1-factor of $ G$. The Hall condition for $ A\subseteq V(G)$ then follows, since there are $ k \left| A \right|$ edges between $ A$ and $ \displaystyle\bigcup_{v\in A}^{} N_v$ (because $ G$ is $ k$-out-regular), and each $ u\in \displaystyle\bigcup_{v\in A}^{} N_v$ can take at most $ k$ of those (because $ G$ is $ k$-in-regular).

However, it's not immediately obvious that we can reduce the undirected case to this one. Fortunately, we can do it!

Proposition 7.

Every $ 2k$-regular graph admits an orientation that turns it into a $ k$-regular digraph.

Proof 4.

We can use an Eulerian tour. Every regular graph of even degree has an Eulerian tour which starts and ends at the same vertex and visits every edge. It follows that if we orient the graph according to an Eulerian tour, every vertex must have the same number of in- and out-edges, since we enter it and leave it the same number of times.

References

[CaH85]. Chetwynd, Amanda G and Hilton, AJW. Regular graphs of high degree are 1-factorizable. Oxford University Press. Proceedings of the London Mathematical Society. 2. 3. 193--206. 1985