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

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

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