Дано n точек, n > 4. Докажите, что можно соединить их стрелками так, чтобы из каждой точки в любую другую можно было попасть, пройдя либо по одной стрелке, либо по двум (каждые две точки можно соединить стрелкой только в одном направлении; идти по стрелке можно только в указанном на ней направлении).
Решение
Индукция по n. База. При n = 5 требуемый граф представлен на рис. слева.
Шаг индукции. Рассмотрим n + 1 точку. Пусть n из них уже соединены – получился граф с n вершинами. Можно считать, что каждые две из этих n точек соединены стрелкой: иначе проведём все недостающие стрелки (направив их в любую сторону), условие тем более будет выполняться. Обозначим (n+1)-ю точку через C и рассмотрим два случая.
1) n чётно. Разобьём n точек на пары. Пусть {Ak, Bk} – одна из пар (1 ≤ k ≤ n/2) и из Ak идёт стрелка в Bk. Тогда проведём из C стрелку в Ak и из Bk проведём стрелку в C (рис. в центре). Так проделаем для каждой пары. Новый граф с n + 1 вершиной построен. Пусть X, Y – две любые различные его вершины.
Если и X и Y не совпадают с C, то из X в Y можно пройти (не более чем за два «хода») по индукционному предположению.
Пусть X или Y совпадает с C. Тогда другая из этих точек (Y или X) входит в какую-то пару из тех, на которые мы разбили первые n точек. Таким образом, X и Y – это какие-то две из трёх точек, изображенных на центральном рисунке. Глядя на этот рисунок, легко перебрать все возможные варианты и убедиться, что требование выполняется.
2) n нечётно. Выберем любую вершину A1. Она соединена стрелками со всеми остальными вершинами: A2, …, An. Из A1 выходят не менее чем две стрелки или в A1 входят не менее чем две стрелки (так как n > 4).
Пусть из A1 выходят не менее чем две стрелки (второй случай аналогичен) – в вершины A2, A3. Остальные вершины разобьем на пары. Теперь соединим стрелками новую вершину с тройкой A1, A2, A3 – как показано на рис. справа, а со всеми парами – как показано на рис. в центре. Как и в случае а), легко доказать, что полученный граф удовлетворяет условию задачи.