137
правок
Изменения
→2-факторизация
Объединим вершины <tex>v^-</tex> и <tex>v^+</tex> обратно в вершину <tex>v</tex>. Так как в графе <tex>H</tex> каждой вершине было инцидентно <tex>1</tex> ребро, то после объединения в графе <tex>G</tex> каждой вершине будет инцидентно <tex>2</tex> ребра.
Если <tex>G</tex> несвязен, то аналогичные рассуждения можно провести для каждой его [[Отношение связности, компоненты связности#def def2 | компоненты связности]], и, таким образом, найти <tex>2</tex>-фактор в каждой его компоненте связности. Тогда каждой вершине каждой его компоненты связности будет инцидентно <tex>2</tex> ребра, значит, каждой вершине <tex>G</tex> будет инцидентно <tex>2</tex> ребра, значит, в <tex>G</tex> существует <tex>2</tex>-фактор.
}}
