Индукция в графах и теорема Турана

Индукция по числу городов.

База. Если в городе имеются всего два города и то утверждение очевидно: по условию из в ведут не менее двух дорог; поэтому достаточно установить по одной из этих дорог движение от к а по второй — от к мы сможем проехать от каждого города до любого, отличного от него.

Шаг индукции. Рассмотрим страну, имеющий город и два соседних из этих городов — города и соединённые улицей Поскольку после введения на дороге (при её ремонте) одностороннего движения — скажем, от к — проехать от к было возможно, то из в ведёт некоторая не включающая дороги “цепочка” дорог (эту “цепочку” можно считать не имеющей самопересечений). Таким образом, мы приходим к существованию в стране “кольца” — замкнутой сети дорог, ведущей из в а затем (через ряд “промежуточных” городов) — снова в

Рассмотрим теперь новую страну, план которой получается из плана прошлой страны “склеиванием” всех городов нашего кольца в один город из которого исходят все дороги реально “упирающиеся” в кольцо Число городов такоой условной страны меньше поэтому по предположению индукции в нём можно ввести по всем дорогам одностороннее движение с соблюдением требований задачи. Если мы затем оставим движение по всем не входящим в кольцо дорогам таким же, каким оно было в этой новой стране, а по кольцу пустим движение в одном (безразлично каком!) направлении, то на всех городах страны будет установлено одностороннее движение — и притом с каждого города можно будет проехать в любой другой.