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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.