Question 1. Let $\Gamma=(V,E)$ be a connected 
graph with $n$ vertices, all of degree $d\geq 4$. Assume every vertex has $d$ distinct neighbors. (We can think of $d$ as being much smaller than $n$, but not necessarily bounded.)


As is customary, for a set of vertices $W\subset V$, we define the *boundary* $\partial W$ to be the set of vertices not in $W$ that have at least one neighbor in $W$. Call a set $W\subset V$ *connected* if the corresponding subgraph $\Gamma|\_{W}$ of $\Gamma$ is connected.
Write $|S|$ for the number of elements of a set $S$.


What sort of lower bound can we give on $\max\_{\text{$W\subset V$ connected}} |\partial W|$?


Question 2. What happens if you remove the assumption that all vertices have the same degree, and just require them to have degree between $3$ and $d$, say?



Existence of connected component with large boundary?
If all degrees are at least 3, there exists a spanning tree with at least $n/4+2$ leaves (D. J. Kleitman and D. B. West, [Spanning trees with many leaves](https://doi.org/10.1137/0404010), SIAM J. Disc. Math. 4(1991), 99-106), the сomplement of these leaves gives you a connected set with boundary of size at least $n/4+2$.


