Weak $1$-factorizability

Question

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?

Answer 1

The 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$.
(1) If $E(G)$ can be partitioned into $t$ maximal matchings, then $n\le t\le2n-1$.
(2) $E(G)$ can be partitioned into $2n-1$ maximal matchings if and only if $G$ is a covering graph of the odd graph $O_n$ also known as the Kneser graph $K(2n-1,n-1)$.

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?