Если у графа все простые циклы имеют чётную длину, то этот граф не имеет ни одного цикла нечётной длины.

Доказательство:

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

Тогда этот непростой цикл нечётной длины можно разбить на 2 цикла, один из которых имеет чётную длину, а другой нечётную (потому что нечётное число можно разбить на 2 слагаемых, одно из которых – чётно, а другое – нечётно). Из этих двух циклов тот, который имеет нечётную длину, также разобьём на два цикла, один из которых четен, другой нечетен и т.д, пока не дойдём до двух простых циклов, один из которых чётной длины, а второй – нечётной. Это противоречит условию. чтд

Две вершины А и B графа называются связными, если существует путь, соединяющий эти вершины и несвязными в противном случае.

Граф называется связным, если любые две его вершины связные.

Теорема 5:

Связный граф G является простым циклом тогда и только тогда, когда степень каждой его вершины равна 2.

Доказательство:

1. пусть G – связный граф, являющийся простым циклом, тогда он не может проходить ни через одну из своих вершин 2-ды, тогда в каждую вершину входит одно ребро и выходит одно ребро, а значит стА_i=2.

2. Пусть у связанного графа стА_i=2.

Начнём цикл из любой вершины А по одному из двух рёбер выходящих из этой вершины. Мы окажемся в B, из B также выйдем по второму рёбру и окажемся в С и т.д. продолжим эту ситуацию, тогда мы окажемся в любой вершине и можем закончить в А, т.к. у А – 2 ребра.

Таким образом построили простой цикл. чтд