Connected sets with a large boundary in a privileged set

Question

Let $G=(V,E)$ be a connected, undirected graph. Define the boundary $\partial S$ of a set $S\subset V$ to be the set of all $v\notin S$ joined to $S$ by an edge, i.e. $$\partial S = \{v\not \in S: \exists v'\in S s.t. {v,v'}\in E\}.$$ We know that, if there are at least $n$ vertices of degree $\geq 3$ in $G$, then there is a set $S\subset V$ such that the subgraph $G|_{S}$ is connected and $\partial S$ has $\geq \frac{n}{4}+2$ elements.

(Proof: construct a spanning tree with $\geq \frac{n}{4}+2$ leaves, as per Spanning trees: the last darn $1/4$ . Then take $S$ to be the set of internal nodes. Thanks to F. Petrov (Existence of connected component with large boundary?).)

Let $V'\subset V$ be set of $m$ vertices, all of degree $\geq 3$. Is there a set $S\subset V$ such that $G|_S$ is connected and $\partial S\cap V'$ has $\geq \delta m$ elements, where $\delta=1/100$, say?

Answer 1

The following seems to be a counterexample. Let $G$ be the graph consisting of

• A cyclic graph with $\mathbb{Z}/2 m \mathbb{Z}$ as its set of vertices (in that order); this will be our set $V'$;
• $m$ copies of $K_4$, with each one having one vertex attached to some $2j\in \mathbb{Z}/2m\mathbb{Z}$ and another vertex attached to $2j+1\in \mathbb{Z}/2m\mathbb{Z}$.

If a set $S$ is such that $G|_\mathbb{S}$ is connected, and it contains, on the one hand, either $2 a$, $2 a+1$, or a vertex in the copy of $K_4$ attached to $2a$ and $2a+1$, and, on the other hand, either $2 b$, $2b+1$, or a vertex in the copy of $K_4$ attached to $2 b$ and $2b+1$, then either $G|_S$ contains every edge $(2a+1,2a+2), (2a+3,2a+4),\dotsc,(2b-1,2b)$, or $G|_S$ contains every edge $(2b+1,2b+2),\dotsc,(2a-1,2a)$ (otherwise $G|_S$ would not be connected). Hence, either $\{2a+1,2a+2,\dotsc,2b\}\in S$ or $\{2b+1,2b+2,\dotsc,2a\}\in S$. In any event, at most two elements of $V'$ will lie in $\partial S$.