Письменный разбор экзамена ШАД. Задача 8. Рёбра в графе

В этом году мы решили помочь тем, кто готовится к поступлению в Школу анализа данных, и поделиться решениями нескольких заданий из вариантов письменного экзамена, демонстрирующими полезные приёмы.

[kea]

После инверсии формулировка "не соединённая с 4 другими" не совсем понятна, должна быть что-то вроде "не соединенная ни с одной из 4"

[anmill]

Интересно, но ничего не понятно. Спасибо пожалуйста

[belkka]

Для полноты решения надо ещё доказать что граф в котором отсутствуют только 20 несмежных рёбер удовлетворяет условию. Действительно, в любой группе из нечётного числа (в частности, пяти) вершин в таком графе всегда найдётся хоть одна без своего "партнёра" (если "партнёром" называть ту единственную другую вершину, с которой она не соединена). Это и значит что она соединена со всеми остальными. Лайк этому комментарию, если считаешь что без этого замечания решение нельзя считать полным. Дизлайк если это доказывать необязательно.