Return to Answer

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_0,M_1,M_2,M_3$ where
$M_0=\{\{wx,yz\},\{wy,xz\},\{wz,xy\}\}$;
$M_1=\{\{vw,xy\},\{vx,wz\},\{vy,xz\},\{vz,wx\}\}$;
$M_2=\{\{vw,xz\},\{vx,yz\},\{vy,wz\},\{vz,wy\}\}$;
$M_3=\{\{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; 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 quite easy to construct a $3$-regular infinite connected graph $G$ such that $E(G)$ can't 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 every $3$-regular infinite connected graph can be partitioned into $4$ maximal matchings?

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?

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)$.

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

P.S. 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; 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. By the way, the edges of the Petersen graph can also be partitioned into $4$ maximal matchings.)

Remark. It's quite easy to construct a $3$-regular infinite connected graph $G$ such that $E(G)$ can't 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 every $3$-regular infinite connected graph can be partitioned into $4$ maximal matchings?

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_0,M_1,M_2,M_3$ where
$M_0=\{\{wx,yz\},\{wy,xz\},\{wz,xy\}\}$;
$M_1=\{\{vw,xy\},\{vx,wz\},\{vy,xz\},\{vz,wx\}\}$;
$M_2=\{\{vw,xz\},\{vx,yz\},\{vy,wz\},\{vz,wy\}\}$;
$M_3=\{\{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; 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 quite easy to construct a $3$-regular infinite connected graph $G$ such that $E(G)$ can't 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 every $3$-regular infinite connected graph can be partitioned into $4$ maximal matchings?

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)$.

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

P.S. 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; 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 quite easy to construct a $3$-regular infinite connected graph $G$ such that $E(G)$ can't 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 every $3$-regular infinite connected graph can be partitioned into $4$ maximal matchings?

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)$.

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

P.S. 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; 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. By the way, the edges of the Petersen graph can also be partitioned into $4$ maximal matchings.)

Remark. It's quite easy to construct a $3$-regular infinite connected graph $G$ such that $E(G)$ can't 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 every $3$-regular infinite connected graph can be partitioned into $4$ maximal matchings?