Задача 085 — Задачи на Графы

Архипелаг состоит из 1000 островов, некоторые пары которых соединены мостами, причём от любого острова можно добраться по мостам до любого другого. Оказалось, что для любых четырёх островов $A, B, C, D$ таких, что есть мост между $A$ и $B$ , между $B$ и $C$ , между $C$ и $D$ , также есть мост между $A$ и $C$ или между $B$ и $D$ . Докажите, что есть остров, соединённый мостами со всеми остальными.

Подсказка

Решение

Рассмотрим граф, в котором вершины — архипелаги, ребра — мосты. Выберем в этом графе вершину наибольшей степени, назовем её $B$ . Предположим, что $B$ соединена не со всеми вершинами. Так как граф связный, какая-то вершина, соединенная с $B$ , должна быть соединена с вершиной, не соединенной с $B$ (иначе мы не доберемся от $B$ до тех вершин, с которыми она не соединена). Пусть $B$ соединена с $C, C$ соединена с $D$ , но $B$ не соединена с $D$ . Теперь для любой вершины $A$ , которая соединена с $B$ , мы можем применить условие задачи для пути $A-B-C-D$ и получить, что $A$ соединена с $C$ (так как между $B$ и $D$ нет ребра). Таким образом, $C$ соединена с $B$ , со всеми вершинами, с которыми соединена $B$ , и ещё с вершиной $D$ . Это значит, что её степень больше степени $B$ , что противоречит нашему изначальному выбору. Таким образом, вершина наибольшей степени обязана быть соединена со всеми остальными вершинами.