Количество вершин нечётной степени в любом графе всегда чётно из-за теоремы о рукопожатиях. 2

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