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

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

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

Оценка. Предположим $e \le 2v - 3$. Пронумеруем вершины от $1$ до $v$. Рассмотрим граф $G$, в котором рёбрами 1-я вершина соединена с каждой, их будет $v-1$. Теперь пусть 2-я вершина соединена с вершинами $1,3,\dots, e-v+3 \le 2v-3-v+3 = v$. Каждый цикл содержит одну из вершин $3,4,\dots,v$, у каждой из которых степень равна $2$. Значит, после удаления этого цикла эта вершина станет изолированной, т.е. $G$ не связен.

Пример. У данного графа $G$ рассмотрим остовное дерево $T$ и отметим все его рёбра. Нарисуем граф $A$ на $v-1$ вершине — это все вершины $G$ кроме $i$-й, а рёбра — все неотмеченные рёбра графа $G$ (Б.О.О. все рёбра, входящие из вершины $i$, отмечены). В нём $e - (v-1) \ge v-1$ рёбер, вершин в нём не меньше числа рёбер, а значит, в нём найдётся цикл. Тогда, удалив этот цикл, мы получим граф, у которого есть порождённое дерево $T$, а значит, он связан.