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

Доказательство 1: Подсчет рёбер

Рассмотрим конечный граф ( G ) с вершинами ( V ) и рёбрами ( E ). По определению, степень вершины ( v ), обозначаемая как ( \deg(v) ), это количество рёбер, инцидентных этой вершине.

Обозначим количество вершин с нечетной степенью как ( k ). Теперь рассмотрим сумму всех степеней вершин в графе. По теореме о Handshaking (рукопожатии) эта сумма равна удвоенному количеству рёбер:

[
\sum_{v \in V} \deg(v) = 2|E|.
]

Теперь мы можем разделить сумму степеней на два:

[
\sum{v \in V} \deg(v) = \sum{v \in V, \deg(v) \text{ четна}} \deg(v) + \sum_{v \in V, \deg(v) \text{ нечетна}} \deg(v).
]

Заметим, что сумма степеней вершин с четной степенью всегда четна (поскольку четные числа). Теперь рассмотрим значения степеней вершин с нечетной степенью. Каждая такая степень ( \deg(v) ) является нечетным числом, и сумма нечетного количества нечетных чисел (а их число равно ( k )) также будет нечетной, если ( k ) нечетно, и четной, если ( k ) четно.

Следовательно, поскольку вся сумма ( \sum_{v \in V} \deg(v) ) четная, это означает, что ( k ) должно быть четным.

Доказательство 2: Использование инварианта

Другой метод доказательства заключается в рассмотрении инварианта на уровне рёбер. Обозначим количество вершин с четной степенью как ( e ) и количество вершин с нечетной степенью как ( o ).

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

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

Более формально, рассмотрим процесс добавления вершин и рёбер к графу, сохраняя его связным. Каждое добавление рёбер или изменение количества рёбер сохраняет четность количества нечетных вершин в графе. Таким образом, при каждой операции мы сохраняем парность числа этих вершин.

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

В итоге, мы еще раз приходим к выводу, что в любом конечном графе количество вершин с нечетной степенью четно.

Заключение

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