Так как согласно [[Эйлеровость графов#eulerTheorem | критерию Эйлеровости]] граф <tex>G</tex> имеет эйлеров цикл <tex>v_0e_1 \cdots e_lv_l</tex>, где <tex>v_0 = v_l</tex>.
Разделим Будем строить граф <tex>H</tex> следующим образом: разделим каждую вершину графа <tex>G</tex> <tex>v</tex> на две, назовём их <tex>v^-</tex> и <tex>v^+</tex>. Заменим каждое ребро в эйлеровом обходе <tex>v_iv_{i+1}</tex> на ребро <tex>v_i^-v_{i+1}^+</tex> [[Файл:2-фактор(1).png|300px|thumb|center|Пример регулярного графа чётной степени. В нём есть эйлеров цикл <tex>1</tex>{{---}}<tex>2</tex>{{---}}<tex>3</tex>{{---}}<tex>4</tex>{{---}}<tex>1</tex>]] [[Файл:2-фактор(2).png|300px|thumb|center|Соответствующий ему граф <tex>H</tex>]] Получившийся граф является <tex>k</tex>-регулярным, и по [[Рёберная раскраска двудольного графа#lem2 | лемме о существовании совершенного паросочетания в регулярном двудольном графе]] в нём есть совершенное паросочетание, то есть <tex>1</tex>-фактор. Объединим вершины <tex>v^-</tex> и <tex>v^+</tex> обратно в вершину <tex>v</tex>. Так как в графе <tex>H</tex> каждой вершине было инцидентно <tex>1</tex> ребро, то после объединения в графе <tex>G</tex> каждой вершине будет инцидентно <tex>2</tex> ребра.
}}
