Доказательство окончено. Из этого, в частности, следует, что сумма произвольных циклов, все ребра которых различны, всегда представляет четный граф

Из этого, в частности, следует, что сумма произвольных циклов, все ребра которых различны, всегда представляет четный граф. При этом каждая компонента связности суммы таких циклов представляет собой четный граф, в котором по теореме Эйлера имеется цикл Эйлера.

В общем случае сумма простых циклов может оказаться несвязной. Например, это так для графов, изображенных на рис. 5.23.

+ =

С ₁ С ₂ С ₁ + С ₂

Рис. 5.23

Рассмотрим вопрос о нахождении такого семейства F - простых циклов в произвольном графе G, что любой простой цикл в этом графе является суммой некоторых из циклов семейства F.