ВсОШ 2026, 10 класс, задача 6
В стране ровно городов, некоторые пары городов соединены двусторонними авиалиниями. Известно, что для любого натурального выполнено следующее утверждение: «Если выбрать любое множество из городов, то найдётся хотя бы городов, не принадлежащих , каждый из которых соединён авиалинией хотя бы с одним городом из ». Какое наименьшее количество авиалиний может быть в этой стране?
Ответ: .
Решение. Положим , так что в нашем графе вершин.
Оценка. Докажем, что в графе степени всех вершин хотя бы . Отсюда будет следовать, что количество ребер не меньше
Пойдём от противного: пусть у некоторой вершины степень не больше . Тогда можно взять множество из вершин, каждая из которых не соединена с . Для множества условие не будет выполнено. Противоречие.
Пример. В качестве примера можно взять , полный двудольный граф на вершинах с равными долями. Нетрудно проверить, что он удовлетворяет условию: если множество вершин принадлежит одной доле, то любая из вершин другой доли соединена с любой вершиной из ; если же в есть вершины из обеих долей, то любая вершина, не лежащая в , соединена хотя бы с одной вершиной из , лежащей в противоположной доле.