Теория:
В работе с графами важно понимать не только что такое вершина и её степень, но и к какому виду эта вершина относится.
Вспомним правило.
Степенью (или порядком) вершины называется количество рёбер, которые выходят из этой вершины.
Каждую вершину графа можно отнести к одному из двух видов вершин.
Вершина графа называется чётной, если её степень чётна, и нечётной, если её степень нечётна.
Например, на рисунке \(1\) вершины A, D — чётные, так как имеют степени \(2\) и \(4\) соответственно, а вершины B, C, E, K, N, F — нечётные, так как вершины B, E, K, N, F имеют степень \(1\), а вершина C — степень \(3\).
В прошлой теме мы, исходя из примеров, сформулировали и применяли для решения задач правило нахождения количества вершин, часто это правило называют леммой о рукопожатиях. Сформулируем его ещё раз.
Лемма о рукопожатиях.
Сумма степеней всех вершин графа равна удвоенному количеству рёбер.
Важную роль играет и следствие из леммы о рукопожатиях, оно позволяет определять, существует ли граф, если известно только количество нечётных вершин в графе.
Следствие. Число нечётных вершин графа всегда чётно.