Deletion a tree from a $n$-connected graph preserving connectivity

E. Yu. Aksenova^a, D. V. Karpov<sup>b

a</sup> Президентский Физико-математический лицей No. 239, ул. Кирочная, д. 8, 191028, Санкт-Петербург, Россия
^b St. Petersburg Department of Steklov Mathematical Institute of Russian Academy of Sciences

Abstract: Let $G$ be a $n$-connected graph and let $T$ be an arbitrary tree with $n+1$ vertices, different from $K_{1,n}$. It is proved that $G$ has a subgraph $H$ isomorphic to $T$ such that the graph $G-H$ is connected. It is proved that any $3$-connected graph $G$ has a subgraph $H$ isomorphic to $K_{1,3}$ such that the graph $G-H$ is connected. Let $n \ge 4$ and let $G$ be a $n$-connected graph $G$ which has a vertex of degree more than $n$. We prove that $G$ has a subgraph $H$ isomorphic to $K_{1,n}$ such that the graph $G-H$ is connected. It is shown that, for $n=4$ and $n\ge 6$, the similar statement for $n$-regular $n$-connected graphs fails. It is proved that, for any $n$-connected graph $G$ and any $k\le 2n-1$, we can delete from $G$ a simple path on $k$ vertices such that the obtained graph is connected. It is shown that the similar statement for a path on $2n$ vertices fails.

Key words and phrases: vertex connectivity, $n$-connected graph, tree.

UDC: 519.173.1

Received: 20.11.2025