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$, а значит, он связан.