Ориентированные графы

Докажем, что
    а) от каждой зелёной площади можно доехать до синей;
    б) от синей площади можно доехать до любой зелёной.
  Условимся обозначать направление движения на улицах стрелками.

  а) Предположим, что от зелёной площади A₁ нельзя доехать до синей площади. Поскольку уехать с площади A₁ можно, то от неё, проехав по одной улице, мы доедем до зелёной площади A₂. От площади A₂ тоже нельзя доехать до синей площади. Выехав с неё, мы доедем до площади A₃, потом до A₄ и т.д. Проехав по n улицам, мы вернёмся на площадь A₁ и убедимся, что стрелки в городе расставлены так, как на рисунке. Но тогда на синюю площадь нельзя приехать, что противоречит условию.

  б) Изменим направления всех стрелок. Полученная схема движения тоже удовлетворяет условию. Поэтому, как показано в а), при этой расстановке стрелок от каждой зелёной площади можно доехать до синей. Но это означает, что при старой расстановке стрелок от синей площади можно было доехать до любой зелёной.

Индукция по n. База. При n = 5 требуемый граф представлен на рис. слева.
Шаг индукции. Рассмотрим n + 1 точку. Пусть n из них уже соединены – получился граф с n вершинами. Можно считать, что каждые две из этих n точек соединены стрелкой: иначе проведём все недостающие стрелки (направив их в любую сторону), условие тем более будет выполняться. Обозначим (n+1)-ю точку через C и рассмотрим два случая.

1) n чётно. Разобьём n точек на пары. Пусть  {A_k, B_k}  – одна из пар  (1 ≤ k ≤ ⁿ/₂)  и из A_k идёт стрелка в B_k. Тогда проведём из C стрелку в A_k и из B_k проведём стрелку в C (рис. в центре). Так проделаем для каждой пары. Новый граф с  n + 1  вершиной построен. Пусть X, Y – две любые различные его вершины.
  Если и X и Y не совпадают с C, то из X в Y можно пройти (не более чем за два «хода») по индукционному предположению.
  Пусть X или Y совпадает с C. Тогда другая из этих точек (Y или X) входит в какую-то пару из тех, на которые мы разбили первые n точек. Таким образом, X и Y – это какие-то две из трёх точек, изображенных на центральном рисунке. Глядя на этот рисунок, легко перебрать все возможные варианты и убедиться, что требование выполняется.
  2) n нечётно. Выберем любую вершину A₁. Она соединена стрелками со всеми остальными вершинами: A₂, …, A_n. Из A₁ выходят не менее чем две стрелки или в A₁ входят не менее чем две стрелки (так как  n > 4).
  Пусть из A₁ выходят не менее чем две стрелки (второй случай аналогичен) – в вершины A₂, A₃. Остальные вершины разобьем на пары. Теперь соединим стрелками новую вершину с тройкой A₁, A₂, A₃ – как показано на рис. справа, а со всеми парами – как показано на рис. в центре. Как и в случае а), легко доказать, что полученный граф удовлетворяет условию задачи.

Пусть удалена дорога, ведущая из А в В. Рассмотрим произвольные два города C и D, отличные от А и В.
1) До удаления дороги АВ из C в D можно было проехать по одной или двум дорогам. Очевидно, ни одна из них не совпадает с АВ. Поэтому удаление дороги АВ не повлияет на проезд из C в D.
2) После удаления дороги АВ по условию остался путь из A в B. Пусть E – последний город на этом пути перед B. Как показано выше, из C в E можно проехать не более чем по двум дорогам. Значит, из C в B можно проехать не более чем по трём дорогам.
Аналогично доказывается, что из А можно проехать в D не более чем по трём дорогам.
3) До удаления дороги АВ из A в E можно было не более чем по двум дорогам. Очевидно, ни одна из них не совпадает с АВ. Поэтому после удаления дороги АВ из А в В можно проехать не более чем по трём дорогам (по маршруту АEВ).

Пусть n – число сторон данного многоугольника, а k – число вершин, в которые входит по две стрелки. Всего стрелок – n, из них 2k стрелок входят в данные k вершин, остальные n – 2k стрелок входят еще в n – 2k вершин (в каждую – по одной). Остаётся n – k – (n – 2k) = k вершин, в которые не входит ни одной стрелки, то есть из которых выходит по две стрелки.