Количество рёбер в графах зависит от чётности количества вершин, потому что количество рёбер равно половине суммы степеней всех вершин графа. 13

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

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