Удаление дерева из $n$-связного графа с сохранением связности

Е. Ю. Аксенова^a, Д. В. Карпов<sup>b

a</sup> Президентский Физико-математический лицей No. 239, ул. Кирочная, д. 8, 191028, Санкт-Петербург, Россия
^b С.-Петербургское отделение Математического института им. В А. Стеклова РАН, Фонтанка 27, 191023 С.-Петербург, Россия

Аннотация: Пусть $G$ – $n$-связный граф, а $T$ – произвольное дерево на $n+1$ вершине, отличное от $K_{1,n}$. Доказано, что $G$ имеет изоморфный $T$ подграф, в результате удаления которого получается связный граф. Доказано, что из любого трехсвязного графа можно удалить подграф $K_{1,3}$ так что граф остается связным, а при $n \ge 4$ из любого $n$-связного графа, имеющего вершину степени более $n$, можно удалить подграф $K_{1,n}$ так, что граф останется связным. Показано, что при $n=4$ и $n\ge 6$ для $n$-регулярных $n$-связных графов аналогичное утверждение неверно. Доказано, что для любого $k\le 2n-1$ из $n$-связного графа можно удалить путь на $k$ вершинах так, что граф останется связным. Показано, что аналогичное утверждение для пути на $2n$ вершинах неверно. Библ. – 7 назв.

Ключевые слова: вершинная связность графа, $n$-связный граф, дерево.

УДК: 519.173.1

Поступило: 20.11.2025