Утверждение: регулярный связный граф степени два - цикл.
Доказательство:
Индукция по числу вершин.
База: треугольник.
Индукционный шаг: пусть для n-вершинного графа это верно (n ≥ 3). Рассмотрим граф из n + 1 вершины. Выберем любую вершину, удалим её саму и два ребра к её соседкам. Соседок соединим одним ребром. Получится регулярный граф степени 2 из n вершин. По индукционному предположению это цикл. Откатим наши изменения, получим цикл из n + 1 вершины. Доказано.
Утверждение: в связном графе со всеми чётными степенями вершин есть эйлеров цикл.
NB Доказательство ведётся для мультиграфов.
Доказательство: индукция по числу рёбер, число вершин (m) фиксировано.
База: граф-цикл из m рёбер.
Индукционный шаг: Пусть для всех графов с n рёбрами есть эйлеров цикл. Рассмотрим граф с n + 1 ребром. В нём есть вершина степени больше двух (иначе это был бы цикл, а он не цикл, так как n + 1 > m). Выберем любые два ребра из этой вершины, удалим их, соседок в которые шли эти рёбра соединим одним новым ребром. Получится связный (мульти)граф с n рёбрами. По индукционному предположению в нём есть эйлеров цикл. В этот цикл входит новое ребро между соседками. Заменим его парой рёбер которые мы удаляли. Получится эйлеров цикл для графа с n + 1 ребром. Доказано.
Утверждение: если в связном графе все вершины кроме двух имеют чётную степень, то в нём есть эйлеров путь начинающийся и завершающийся в этих двух вершинах.
Доказательство:
Соединим эти две вершины новым ребром. Получим связный (мульти)граф со всеми чётными степенями. В нём есть эйлеров цикл. В него входит новое ребро. Удалим его. Получим эйлеров путь в исходном графе. Доказано.