1
$\begingroup$

Definition: A $k$-factor of a graph is a spanning $k$-regular subgraph.

Definition: A $k$-factorization of a graph is a partition of the edge set into $k$-factors.

Petersen's celebrated theorem says that a $2m$-regular graph has a $2$-factorization. A corollary is that a $2m$-regular graph also has a $2k$-factor for any $k \leq m$, since you can take the union of $k$ $2$-factors from the factorization.

My question is whether the converse of the corollary is true, that is -

can every $2k$-factor of a $2m$-regular graph be written as a union of $k$ factors from a $2$-factorization?

$\endgroup$

1 Answer 1

5
$\begingroup$

If I understand your question correctly, the answer is yes and follows directly from Petersen.

Let $H_1$ be your $2k$-factor, and $H_2$ the $(2m-2k)$-factor that remains of $G$ after deleting the edges of $H_1$. Now apply Petersen to each of $H_1$ and $H_2$ to get $2$-factorizations in each, which combine to a $2$-factorization of $G$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .