Может ли существовать граф, у которого сумма степеней всех вершин равна 25431? (Если да, то запиши в ответе сумму степеней его вершин, если нет, то укажи максимально возможную сумму степеней вершин, меньше числа в условии.)

Question

Вопрос:

Может ли существовать граф, у которого сумма степеней всех вершин равна 25431? (Если да, то запиши в ответе сумму степеней его вершин, если нет, то укажи максимально возможную сумму степеней вершин, меньше числа в условии.)

Ответ:

Accepted Answer

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

Решение:

Число 25431 - нечётное. Ближайшее к нему меньшее чётное число - 25430.

Ответ: , сумма степеней всех вершин равна 25430.

Проверка за 10 секунд: Убедись, что указанное число чётное и меньше исходного.

Лайфхак:

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