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

Докажем утверждение задачи по индукции. Для двух городов утверждение очевидно. Пусть верно для городов, докажем для Выкинем некоторую вершину и все рёбра, с концом в этой вершине. Для оставшегося графа верно предположение индукции, то есть существует вершина такая, что из него можно добраться до любой другой по не более, чем рёбрам. Пусть из вершины напрямую можно добраться в вершины а только через другую вершину в Если из вершины или из какой-нибудь из вершин ребро ведёт в то вершина по-прежнему подходит. Если же во все эти вершины ведут рёбра из то подойдёт вершина в вершины можно попасть непосредственно, а в вершины — через вершины