Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

From this paper we find the quote:

Lemma 1 (Petersen [2]) Every $2r$-regular graph can be decomposed into $r$ disjoint $2$-factors.

They described it as "Petersen’s classic decomposition theorem about regular graphs of even degree". The reference [2] is:

J. Petersen, Die Theorie der Regularen Graphen, Acta Math. 15 (1891), 193-220.

I don't have access to this paper, nor would I think it would do me much good, since the title suggests it's not in English.

Question: Where else can I find an English language proof of this result?

share|cite|improve this question
Here is a link to the article: J. Petersen, Die Theorie der regulären Graphs which is indeed in German. – Martin Jan 22 '13 at 8:23

I am not sure if this suits you since the disjoint condition is omitted but in

  • Laszlo Lovász; Combinatorial Problems and Exercises (2nd edition). North-Holland, Amsterdam (page 61. exercise 40.)

there is the following exercise (with hints and proofs included)

Every $2r$ regular graph is the union of $r$ 2-factors.

I am not sure if the disjoint part of your claim is just part of a different definition of factors than the one used in Lovász or if there is a way to modify the proof there to show this additional condition.

share|cite|improve this answer
Hmm... I think you get the "disjoint" property for free -- if they weren't disjoint, the union wouldn't be a $2r$-regular graph. – Douglas S. Stones Jan 22 '13 at 12:08

You can find it in Reinhard Diestel's "Graph Theory" textbook (Corollary 2.1.5 in the 4th edition).

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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