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

Для начала переведем задачу на язык графов. Города будут вершинами, а дороги будут ребрами. Из условия следует, что не существует вершины, которая не соединена с тремя другими вершинами, иначе мы бы взяли эту вершины и трех ее не соседей в четверку и получили противоречие. Теперь докажем по индукции, что в графе на вершинах, в котором каждая вершина максимум не соединена с вершинами, есть полный подграф на вершинах. База, если очевидна. Теперь переход. Пусть мы знаем для и хотим доказать для Рассмотрим вершину графа на вершинах. У нее есть минимум соседей. Рассмотрим подграф на этих вершинах и заметим, что для него также выполняется условие, что каждая вершина не соединина максимум с вершинами. Значит, по предположению индукции там есть полный подграф на вершинах. Теперь давайте добавим в этот граф вершину и получим полный подграф на вершине исходного графа.