Sharp Connectivity-Preserving Tree Deletion Bounds

Definitions and mathematical statement

The supplied statement does not explicitly specify whether graphs are finite, simple, and undirected. The following formulation uses those customary conventions provisionally; they require confirmation against the source. A tree is a nonempty connected graph with no cycles, including the one-vertex tree, and $|T|:=|V(T)|$.

For a graph $G$, let $\delta(G)$ denote its minimum vertex degree. For a positive integer $k$, call a graph $H$ $k$-connected if $|V(H)|\geq k+1$ and $H-X$ is connected for every $X\subseteq V(H)$ with $|X|<k$. Interpret $\kappa(H)\geq k$ as this condition, so that the required remaining graph must have at least $k+1$ vertices. Here $G-X$ is the induced subgraph on $V(G)\setminus X$. A copy $S\cong T$ means a subgraph isomorphic to $T$, with no requirement that the copy be induced. These connectivity and copy conventions are also subject to source confirmation.

For each integer $k\geq1$ and each tree $T$, define \[ \begin{aligned} \mathcal A_k(T):=\bigl\{a\in{\mathbb{Z}}_{\geq0}:\;&\text{for every finite simple undirected graph }G,\\ &\bigl(G\text{ is }k\text{-connected and } \delta(G)\geq\lfloor 3k/2\rfloor-1+a\bigr)\\ &\quad\Longrightarrow\ \exists S\subseteq G\ \bigl(S\cong T\ \text{ and }\ \kappa(G-V(S))\geq k\bigr)\bigr\}. \end{aligned} \] Whenever $\mathcal A_k(T)\neq\varnothing$, put \[ g_k(T):=\min\mathcal A_k(T). \] The supplied curation attributes the existence of this finite minimum to Mader; that attribution is recorded here without independent verification.

The question is whether, for every integer $k\geq1$ and every tree $T$, \[ g_k(T)=|V(T)|. \] The supplied record labels the problem partially solved and describes this sharp equality as open in general. These are supplied literature assessments, not mathematical conclusions established by this draft.

Short English statement

For each positive integer $k$ and tree $T$, determine whether the least extra minimum-degree allowance above $\lfloor3k/2\rfloor-1$ that guarantees a copy of $T$ whose vertex deletion preserves $k$-connectivity is exactly $|V(T)|$. The graph-domain and connectivity conventions stated above remain subject to source confirmation.

Sources

• Local UnsolvedMath registry, supplied complete source record: permanent ID $30001431$, exact source problem code catalogue entry, title "Sharp Connectivity-Preserving Tree Deletion Bounds," in the Oberwolfach Reports Open Problems collection. The supplied proposed year is 2010; no individual proposer is identified.
• Supplied report citation: Graph Theory (2010), Oberwolfach Reports, DOI 10.4171/owr/2010/11, pp. 521--580. https://doi.org/10.4171/owr/2010/11. The literature-source list also identifies this as "Oberwolfach Report 11/2010." The supplied background describes these reports as documentation of mathematical workshops and their open-problem discussions.
• Supplied literature source: Tian--Lai--Xu--Meng, "non-separating trees." https://doi.org/10.1016/j.disc.2018.10.001. No fuller bibliographic information is supplied.
• Literature assessment dated exactly 2026-08-21: the supplied curation labels the problem partially solved, attributes existence of $g_k(T)$ and strong special cases to Mader, and says that $g_k(T)=|T|$ for every tree remains open in general. This is supplied dated curation, not independently verified. Its background explicitly requests independent verification of time-sensitive status and cited claims.
• The supplied statement status is corrected_verified. The accompanying supplied verification note says that the mathematical content was checked against the official Oberwolfach report and that notation, context, and question form were normalized without changing the source-level claim. This draft records that assertion without claiming to have visited or independently checked either external source.