Задача

Привет!

На фотографии показано задание на экране телефона. В задании спрашивается, может ли существовать граф, у которого сумма степеней всех вершин равна 22567. Чтобы ответить на этот вопрос, нам нужно вспомнить некоторые основные факты о графах.

Во-первых, степенью вершины в графе называется количество рёбер, инцидентных этой вершине. В неориентированном графе каждое ребро соединяет две вершины, поэтому сумма степеней всех вершин графа всегда чётная, потому что каждое ребро увеличивает сумму степеней на 2 (по 1 для каждой из соединяемых им вершин).

Число 22567 — нечётное, поэтому графа с такой суммой степеней вершин существовать не может. Это основывается на теореме о рукопожатиях, которая говорит, что сумма степеней всех вершин графа равна удвоенному количеству рёбер (так как каждое ребро даёт по единице степени каждой из двух вершин, которые оно соединяет).

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

От