Индукция в графах и теорема Турана

Выделим в нашем графе из вершин остовное дерево.

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

Будем искать вершины с чётной степенью, начиная с нижнего уровня (посмотрели последний уровень, потом предпоследний и так дальше). Если мы не нашли, то задача решена.

Предположим, что мы нашли вершину чётной степени. Предположим, что является корневой вершиной. В таком случае, на втором уровне чётное количество вершин, на третьем — тоже, потому что из каждой вершины второго уровня выходит чётное количество рёбер на третий (потому что степени нечётные). Аналогично чётное количество вершин на всех остальных уровнях. Таким образом, на всех уровнях, кроме первого, чётное количество вершин, но тогда во всём дереве количество вершин нечётно, противоречие.

Следовательно, вершина не корневая. Значит, существует ребро, которое соединяет её с вершиной из уровня выше. Удалим его. Наше дерево распалось на два дерева. Корнем одного из них является и степень каждой вершины в этом дереве нечётная, потому что — первая попавшаяся вершина чётной степени (после удаления ребра её степень также нечётна).

Покажем, что в дереве с корнем чётное количество вершин. Действительно, на первом уровне вершина, на втором — нечётное количество, на всех остальных — чётное, потому что из любой вершины второго и ниже уровней выходит чётное количество рёбер на более низкий уровень, потому что одним ребром она соединена с вершиной из уровня выше, а её степень нечётная. Таким образом, суммарно количество вершин чётное.

Значит и во втором дереве количество вершин чётно, потому что всего вершин Притом в нём не более вершины, то есть для него справедливо предположение индукции.