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

Подсказка 1

Пусть вершины будут городами, а дороги ребрами графа. Если взять треугольник, в одной из вершин которого родной город девы, то очевидно, что монархию она не разрушит. А можно ли продолжать строить треугольники так, чтобы дева, ходя по ним, не могла разрушить монархию?

Подсказка 2

Конечно, можно: нужно просто сделать для них общую вершину! Если n = 2k+1, то треугольников будет k, а если n = 2k, то будет k-1 треугольник и висячая вершинка. Итак, ответ есть, остается проверить его по индукции! Базу надо проверять аккуратно: нам она нужно и при n=1, и при n=2, так как ответ зависит от четности. А как можно осуществить переход?

Подсказка 3

В графе без нечетных циклов, подходящий нашему условию, циклов вообще быть не может! Но тогда ребер в нем не больше, чем n-1. А что делать с нечетным циклом?

Подсказка 4

На самом деле, очевидно, что четных циклов не может быть в нашем графе. Тогда ясно, что две вершины нечетного цикла не могут быть соединены с одной и той же вершиной. Хочется этот цикл убрать, чтобы применить предположение. Для этого его можно стянуть в одну вершину, но сначала нужно проверить посылку индукции! Как это сделать?

Подсказка 5

Предположим, что после стягивания организовался четный цикл. Тогда он проходит через новую вершину V, соответствующую стянутому циклу! Если теперь взять две вершины, связанные с V в новом графе по циклу четной длины, то нетрудно видеть, что и в исходном был такой цикл! Значит, стягивать и применять предположение индукции можно. Как теперь оценить число ребер?

Подсказка 6

Верно! Если после стягивания осталось k вершин, то удалили мы n-k вершин и n-k+1 ребро. И число ребер в графе с k вершинами мы можем оценить! Как теперь получить нужно неравенство для исходного графа?