Let $\Gamma=(V,E)$ be a finite connected graph.


*Pretty standard notation.* Given a set $S\subset V$, write $\Gamma|\_S$ for the restriction of $\Gamma$ to $S$, i.e., the subgraph $(S,\{\{v,w\}\in E: v,w\in S\})$. Write $\partial\_{\textrm{edge}} S$ for the set of edges $\{v,w\}\in E$ with $v\in S$, $w\notin S$. By $|A|$ we mean the number of elements of a set $A$. We denote by $V\setminus S$ the complement $\{v\in V: v\notin S\}$. A *neighbor* of $v\in V$ is a vertex $w$ such that $\{v,w\}\in E$.


**Question.** Is there an absolute constant $c>0$ such that the following statement (Statement A) is true?


*Statement **A**.*  Let $\Gamma=(V,E)$ be a graph whose every vertex has degree $\geq 3$. Then there is an $S\subset V$ such that $\Gamma|\_S$ is connected and
$$|\partial\_{\textrm{edge}} S|\ \geq\ c\cdot|E|.$$




---


It is not hard to reduce statement A to the following:


*Statement **B**.*  Let $\Gamma=(V,E)$ be a graph whose every vertex has degree $\geq 3$. Then there is an $S\subset V$ such that:


* $\Gamma|\_S$ is connected,
* every $v\in V\setminus S$ has a neighbor in $S$,
* the sum of the degrees of the elements of $\ V\setminus S\ $ is $\, \geq\ c\cdot|E|$.




---


I will give below (as an answer) a proof of Statement B for regular graphs, and a proof of the reduction of Statement A to Statement B.



Existence of connected set with large edge boundary
If I am not mistaken, then the following recursive construction disproves statement A:


* Let $G\_1$ consist of a $K\_8$ and an additional vertex $r\_1$ connected to half of the vertices of this $K\_8$
* For $k > 1$ take $2^{2^k}$ copies of $G\_{k-1}$, connect each pair of copies of $r\_{k-1}$ by an edge, and add a vertex $r\_k$ which is incident to half of the copies of $r\_{k-1}$


(connecting $r\_k$ only to half of the copies has the sole purpose of making the numbers in the induction below a bit prettier)


**Claim 1:** $G\_k$ has $\frac{k+3}{2} 2^{2^{k+1}}$ edges and $2\cdot 2^{2^{k+1}}$ of these edges are contained in copies of $G\_1$.


We use induction on $k$. For $k=1$ note that $G\_1$ has ${8 \choose 2} + 4 = 32 = \frac{1+3}{2} 2^{2^{1+1}}$ edges and all of them are contained in a copy of $G\_1$.


For the induction step, note that the $2^{2^k}$ copies of $r\_{k-1}$ form a complete graph. Together with the $\frac{2^{2^k}}{2}$ edges incident to $r\_k$ the number of edges of $G\_k$ which are not contained in any copy of $G\_{k-1}$ is thus $${2^{2^k}\choose 2} + \frac{2^{2^k}}{2} = \frac 12 (2^{2^k})^2 = \frac{2^{2^{k+1}}}{2}.$$
Since $G\_k$ contains $2^{2^k}$ copies of $G\_{k-1}$ each of which by induction hypothesis contains $\frac{k+2}{2} 2^{2^{k}}$ edges, the total number of edges in $G\_k$ is
$$
\frac{2^{2^{k+1}}}{2} + 2^{2^k} \frac{k+2}{2} 2^{2^{k}} = \frac{k+3}{2} 2^{2^{k+1}}
$$
as claimed. For the number of edges contained in a copy of $G\_1$ simply note that all of them are contained in one of the $2^{2^k}$ copies of $G\_{k-1}$ each of which contains $2\cdot 2^{2^k}$ such edges, giving
$$
2^{2^k} \cdot 2 \cdot 2^{2^k} = 2\cdot 2^{2^{k+1}}
$$
such edges in total. This finishes the proof of Claim 1.


**Claim 2:** Let $S$ be a connected set of vertices of $G\_k$ with maximal edge boundary.
Then $V(G\_k) \setminus S$ only consists of vertices in copies of $G\_1$ and $r\_k$, and $r\_1$ is only in $V(G\_k) \setminus S$ if $k=1$. This immediately implies that
$$
 |\partial\_{\text{edge}} S| \leq 2\cdot 2^{2^{k+1}} + \frac{2^{2^k}}{2}.
$$


To show this, we first note that $G\_k$ contains a set $S'$ with $|\partial\_{\text{edge}} S| > 2^{2^{k+1}}$ because in every copy of $G\_1$ we can pick a connected set containing the respective copy of $r\_1$ whose edge boundary contains $19$ of the $32$ edges and then add all vertices not contained in any copy of $G\_1$. In particular, the set $S$ whose edge boundary is maximal must contain at least one of the copies of $r\_{k-1}$, otherwise $S$ would be contained in some copy of $G\_k$ and thus by induction its edge boundary would contain at most $2\cdot 2^{2^{k}} + 2^{2^{k-1}} < 2^{2^{k+1}}$ edges.


Now assume that some copy of $r\_{k-1}$ is not contained in $S$. This copy of $r\_{k-1}$ has at most $2^{2^k}$ neighbours in $S$. Thus adding this copy and a connected subset of the corresponding copy of $G\_{k-1}$ whose edge boundary contains strictly more than $2^{2^{k}}$ edges to $S$ increases the edge boundary while the set stays connected, thereby contradicting maximality of $S$. We have thus shown that $S$ contains all copies of $r\_{k-1}$, and by iterating this argument we see that $S$ must contain all copies of $r\_{j}$ for every $j<k$.


