We say that a simple, undirected graph $G=(V,E)$ is *$1$-factorizable* if there is a partition of $E$ such that every member of the partition is a [perfect matching](https://en.wikipedia.org/wiki/Perfect_matching) of $G$. It is easy to see that any $1$-factorizable graph is regular (every vertex has the same degree).


If $G =(\omega, E)$ is a graph on the vertex set $\omega$ such that every vertex has degree $\aleph\_0$, does this imply that $G$ is $1$-factorizable?


(It is a [fact](https://math.stackexchange.com/questions/3790407/infinite-graph-g-omega-e-with-deltag-aleph-0-and-no-perfect-matchi) that such a graph has a perfect matching.)



Are countable graphs with infinite minimal degree $1$-factorizable?
Yes, any $\aleph\_0$-regular graph $G=(V,E)$ is $1$-factorizable. (By "graph" I mean "simple graph" as in the question. Actually a loopless multigraph is OK provided no two vertices are joined by an infinite number of edges.)


Let $C$ be a set of colors, $|C|=\aleph\_0$. We will color the edges of $G$ with colors from $C$ so that each vertex is incident with just one edge of each color.


Since each connected component of $G$ is countable, we may assume that $|V|=|E|=\aleph\_0$. The coloring will be done in $\omega$ steps, at most one edge being colored at each step, so that at each step only a finite number of edges will have been colored. Fix enumerations $E=\{e\_i:i\in\omega\}$ and $V\times C=\{(v\_i,c\_i):i\in\omega\}$.


At step $2i$ consider the edge $e\_i$. If it has already been colored, do nothing; otherwise, give it a color which has not been given to any edge adjacent to $e\_i$.


At step $2i+1$ consider the pair $(v\_i,c\_i)$. If the vertex $v\_i$ is already incident with an edge of color $c\_i$, do nothing; otherwise find an edge incident with $v\_i$ which has not yet been colored and is not incident with any edge of color $c\_i$, and give it the color $c\_i$.


It is easy to see that this construction can be carried out, and the resulting coloring has the desired properties.


A similar argument shows that every $\aleph\_\alpha$-regular graph is $1$-factorizable.


