A simple, undirected graph is said to be $1$-*factorizable* if there is a partition of the edge set $E$ such that every member of the partition is a perfect matching of $G$. Let us call $G$ *weakly $1$-factorizable* if there is a partition of $E$ into maximal (but not necessarily perfect) matchings.


$K\_3$ is weakly $1$-factorizable, but not $1$-factorizable for the trivial reason that every singleton edge set is a maximal matching and their union is the edge set of $K$, but it has an odd number of vertices and therefore no perfect matching


The graph $(V,E)$ with $V = \{0,1,2,3\}$ and $E = \big\{\{k, k+1\}: k \in \{0,1,2\}\big\}$ has a perfect matching, but it is not *regular* (i.e. not all vertices have the same degree), therefore not $1$-factorizable, but it is weakly $1$-factorizable.


**Question.** What is an example of a weakly $1$-factorizable but not $1$-factorizable regular graph $G=(V,E)$ such that $G$ has a perfect matching?



Weak $1$-factorizability
The [Petersen graph](https://en.wikipedia.org/wiki/Petersen_graph) $G$ is $3$-regular and has a perfect matching but is not $1$-factorizable. To see that $G$ is weakly $1$-factorizable, regard it as the complement of the line graph of $K\_5$. For each vertex $v$ of $K\_5$, let $M\_v$ be the set of all pairs $\{e,f\}$ where $e$ and $f$ are edges of $K\_5$ which are not incident with $v$ and not adjacent to each other in $K\_5$ (so they are adjacent vertices in $G$). Then $M\_v$ is a maximal matching in $G$, and $\{M\_v:v\in V(K\_5)\}$ is a partition of $E(G)$ into $5$ maximal matchings.


Let $V(K\_5)=\{v,w,x,y,z\}$. Plainly $M\_v=\{\{wx,yz\},\{wy,xz\},\{wz,xy\}\}$ is a matching in $G$. To see that $M\_v$ is a maximal matching, consider an edge $e\in E(G)\setminus M\_v$, say $e=\{vw,xy\}$, and observe that $e$ is adjacent to the edge $\{wz,xy\}$ which is in $M\_v$.


**Alternatively,** $E(G)$ can be partitioned into $4$ maximal matchings $M\_1,M\_2,M\_3,M\_4$ where  

$M\_1=\{\{wx,yz\},\{wy,xz\},\{wz,xy\}\}$;  

$M\_2=\{\{vw,xy\},\{vx,wz\},\{vy,xz\},\{vz,wx\}\}$;  

$M\_3=\{\{vw,xz\},\{vx,yz\},\{vy,wz\},\{vz,wy\}\}$;  

$M\_4=\{\{vw,yz\},\{vx,wy\},\{vy,wx\},\{vz,xy\}\}$.


  
The observation that the Petersen graph is weakly $1$-factorizable can be generalized.


**Theorem.** Let $G$ be an $n$-regular (finite or infinite) graph, $2\le n\lt\aleph\_0$.  



**Corollary.** For each $n\ge2$ the odd graph $O\_n$ is weakly $1$-factorizable; in fact, the edges of $O\_n$ can be partitioned into $2n-1$ maximal matchings. (Recall that $O\_2=K\_3$ and $O\_3$ is the Petersen graph.)


**Remark.** It's easy to construct a $3$-regular infinite connected graph $G$ such that $E(G)$ can not be partitioned into $3$ or $5$ maximal matchings; e.g., if $E(G)$ can be partitioned into $5$ maximal matchings, then $G$ must be triangle-free. But perhaps the edges of every $3$-regular infinite connected graph can be partitioned into $4$ maximal matchings?


