математика - Цикл в графе

Хорошая задача, только условие надо подкорректировать. Во-первых, граф следует считать конечным (в противном случае утверждение неверно). Во-вторых, граф может вообще не иметь циклов (дерево), поэтому надо потребовать условия $%a\ge2$%. В-третьих, под графом нужно понимать простой граф, то есть без петель и кратных рёбер.

Вывод здесь можно будет даже несколько усилить, доказав, что найдётся цикл длиной не меньше $%a+1$%.

Вот скорректированная формулировка. Дан простой конечный граф, в котором каждая вершина имеет степень не меньше $%d\ge2$%. Тогда в нём найдётся (простой) цикл длиной не меньше $%d+1$%.

Рассмотрим самый длинный простой путь, то есть такой путь, в котором вершины не повторяются: $%v_1-v_2-\cdots-v_n$%. Это возможно, так как граф конечен. Вершина $%v_1$% имеет степень не меньше двух, поэтому она соединена в графе ещё по крайней мере с одной вершиной. Если это вершина, отличная от вершин рассматриваемого пути, то путь можно удлинить. Следовательно, все соединения $%v_1$% имеют место лишь с вершинами пути. Пусть $%j > 1$% -- максимальный из таких номеров, для которого $%v_1$% соединена с $%v_j$%. При этом возникает простой цикл длиной $%j$%.

Соединений у вершины $%v_1$% может быть не более $%j-1$%: только с вершинами $%v_2$%, ... , $%v_j$%. Следовательно, $%d\le j-1$%, то есть длина цикла $%j\ge d+1$%.