Вершина графа называется нечётной, если её степень нечётна. 1 Степенью вершины называют количество рёбер, которые выходят из этой вершины. 13

Например, на рисунке 1 вершины A, D — чётные, так как имеют степени 2 и 4 соответственно, а вершины B, C, E, K, N, F — нечётные, так как вершины B, E, K, N, F имеют степень 1, а вершина C — степень 3. 1

В любом графе количество вершин нечётной степени всегда чётно. 24 Это следует из леммы о рукопожатиях: сумма степеней всех вершин графа равна удвоенному количеству рёбер. 14