22-я Международная Жаутыковская олимпиада по математике, 2026 год

Дано натуральное $v\geqslant 4$. При каком наименьшем $e$ в каждом связном графе на $v$ вершинах с $e$ рёбрами существует цикл, после удаления всех рёбер которого граф остаётся связным? (После удаления рёбер цикла в графе остаются все его вершины, в том числе и те, в которых удалены все рёбра.) ( Г. Челноков )

Комментарий/решение

Ответ: При 2v - 2.

​Решение

​1. Оценка снизу

​Докажем, что e = 2v - 3 ребер недостаточно.

Пусть в графе с вершинами a_1, a_2, \dots, a_v проведены ребра a_1a_2, a_1a_i и a_2a_i для всех i = 3, 4..., v. Каждый цикл содержит одну из вершин a_3, a_4, ...⁸, a_v, у каждой из которых степень равна 2. Значит, после удаления всех рёбер этого цикла эта вершина станет изолированной, следовательно, граф перестанет быть связным.

Пример для v \le e \le 2v - 4 можно получить из примера выше, удалив несколько рёбер вида a_2a_i с i \ge 3.

​2. Оценка сверху

​Выберем вершину a_1 и рассмотрим дерево T, содержащее все вершины графа (такое дерево называется остовным), в которое входят все рёбра, исходящие из a_1. (Вот как получить такое дерево: если в графе есть цикл, удалим из этого цикла любое ребро, не выходящее из a_1. Связность не нарушится, а количество рёбер уменьшится. Это можно продолжать, пока не останется дерево.)

​Покрасим все v - 1 рёбер дерева T. Если удалить даже все непокрашенные ребра, наш граф останется связным. Поэтому достаточно найти цикл из непокрашенных рёбер.

​Рассмотрим граф G, в котором v - 1 вершин — это все вершины данного графа, кроме вершины a_1, а рёбра — это все непокрашенные рёбра исходного графа (вспомним здесь, что все рёбра, исходящие из a_1, покрашены). Количество этих рёбер равно e - (v - 1) \ge 2v - 2 - v + 1 = v - 1. Видим, что в G количество рёбер не меньше количества вершин, поэтому в нем найдётся некоторый цикл.