# 1- and 2-factorization of graphs and digraphs

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.

**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.

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

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:

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:

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]

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

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:

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!

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