Existence of connected set with large edge boundary 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.
 A: I think I have a counter-example to Statement B:
Start with a $K_r$ and connect every vertex to one vertex of a new $K_4$. This is the graph $\Gamma=(V,E)$, which has $5r$ vertices. Any set $S\subset V$ such that $\Gamma\vert_S$ is connected and $S$ dominates $V/S$ contains at least the vertices of the $K_r$ and their neighbours. Thus, the sum of the degrees of $V/S$ is at most $9r$, but $\lvert E\rvert=r(\frac{r-1}{2}+7)$. Thus, for $r\to\infty$, their ratio goes to $0$.
A: 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$.
A: Reduction of Statement A to Statement B. Let $S$ be as in statement B. Let, at first, $S'=S$. Do the following repeatedly until you cannot: include in $S'$ an element of $V\setminus S'$ having at least twice as many neighbors in $V\setminus S'$ as in $S'$. In the course of this procedure, $\partial_{\textrm{edge}} S'$ increased by at least one-third the sum of the degrees of the vertices newly included in $S'$. At the same time, every vertex still in $V\setminus S'$ has more than one-third of its neighbors in $S'$ (or else the procedure could have gone on) and so $\partial_{\textrm{edge}} S'$ is at least one-third the sum of the degrees of the vertices still not in $S'$. Hence, $\partial_{\textrm{edge}} S'$ is at least one-sixth the sum of the degrees of the elements of $V\setminus S$.
By condition (b) and our construction of $S'$, $\Gamma|_{S'}$ is connected. Hence, statement A holds with $S'$ instead of $S$ and $c/6$ instead of $c$.
A: I assume by degree in V-S you mean the degree in the full graph (not restricted to V-S).
I begin partitioning $V=A \cup B$ of basically the same size (off by at most 1).
Now by your condition the sum of degrees in A and in B is both at least (about) $3/2n$. So if I am not done, it means that there is a vertex in B that has no neighbor in A, and a vertex in A that has no neighbor in B: otherwise one between A and B would be your desired set S.
Now I swap them. In the new partition $A’ \cup B’$ they both have a neighbor in the other club (as each point has degree at least 1). Furthermore I cannot have introduced new points that lack a friend in the other club as both vertices previously lacked friends in the other club.
This way I strictly reduced the number of vertices in each club lacking a friend in the other club. And I can do this until I am done as explained in the first paragraph. So eventually I cannot reduce this size anymore and I am done.
I wanted to write in the comments because there is probably a mistake as it seems too easy, but I don’t have enough reputation yet. So apologies if there is a mistake or I misunderstood your problem.
Edit: I misread the problem; see comments below. Apologies!
A: Proof 1 of Statement B for regular graphs. Let $\Gamma$ be a regular graph of degree $d$. As in F. Petrov's answer to Existence of connected component with large boundary? : by Kleitman and West (https://epubs.siam.org/doi/10.1137/0404010), there exists a spanning tree with $\geq n/4$ leaves, where $n=|V|$. Define $S$ to be the set of non-leaves. Then the total degree of the elements of $V\setminus S$ (that is, the leaves) is $\geq d n/4 = |E|/4$.
Proof 2 of Statement B for regular graphs (from scratch, inspired by Kleitman-West - TL;DR greedy algorithm).  I thought I had a different proof, but I no longer do, or rather, the proof, when corrected, is not really different from Kleitman-West after all.
More to the point: it seems that a proof along these lines is not going to generalize easily to the non-regular case.
It is clear that, for $\Gamma$ not regular, the greedy algorithm could incur a loss at some point and fail to recoup it for more than $C$ steps, for any absolute constant $C$: consider a complete graph of high degree surrounded by many layers of vertices of low degree.
