В некоторой стране 450 городов и 6 авиакомпаний. Каждые два города соединены рейсами одной из шести авиакомпаний. Можно ли утверждать, что найдётся авиакомпания и больше 150 городов, между любыми двумя из которых можно добраться рейсами этой авиакомпании (возможно, с пересадками)?
Построим контрпример. Разобьём города на 6 групп по 75 городов. Назовём эти группы A, B, C, D, E, F.
Внутри каждой группы соединим города рейсами компании номер 1.
Компания номер 2 будет соединять города группы A с городами группы B, C с D, а E с F.
Компания номер 3 будет соединять города группы A с городами группы D, B с E, а C с F.
Компания номер 4 будет соединять города группы A с городами группы C, B с F, а D с E.
Компания номер 5 будет соединять города группы A с городами группы E, B с C, а D с F.
Компания номер 6 будет соединять города группы A с городами группы F, B с D, а C с E.
Таким образом, рейсы компании номер 1 связывают по 75 городов, а рейсы остальных компаний ровно по 150.
Это построение схематично изображено на рисунке. Разные компании обозначены разными цветами. Данный контрпример, разумеется, не единственный.
Ответ: Нет, это не обязательно верно.