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 количество рёбер не меньше количества вершин, поэтому в нем найдётся некоторый цикл.