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 n/4+2$ elements.

(Proof: construct a spanning tree with $\geq 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?).)

Now draw some arrows between adjacent vertices of $G$ - i.e., define a directed multigraph $G'=(V,E')$ with the same set of vertices $V$ as $G$, and such that, if $(v,w)$ is an edge of $G'$, then $\{v,w\}$ is an edge of $G$. Assume that $G'$ is strongly connected. (If it helps, assume as well that the out-degree of every vertex equals its in-degree.) Define the edge out-boundary $\vec{\partial} S$ of a set $S\subset V$ to be the set of arrows coming out of it. It is not hard to prove (using the above) that there is a set $S'\subset V$ such that $G|_{S'}$ is connected and $\vec{\partial} S$ has $\geq (n/4+2)/3$ elements. (In fact, for that, we do not need to assume that $G'$ is strongly connected - we only need to assume that the in-degree of every vertex is positive, together with the assumptions on $G$.)

Can we obtain something stronger, with the right assumptions? Say the number $N$ of arrows coming in and out of vertices that have degree >=3 in G is quite large - much larger than $n$. Can one really not do better than $\geq (n/4+2)/3$?

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 n/4+2$ elements.

(Proof: construct a spanning tree with $\geq 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?).)

Now draw some arrows between adjacent vertices of $G$ - i.e., define a directed multigraph $G'=(V,E')$ with the same set of vertices $V$ as $G$, and such that, if $(v,w)$ is an edge of $G'$, then $\{v,w\}$ is an edge of $G$. Assume that $G'$ is strongly connected. (If it helps, assume as well that the out-degree of every vertex equals its in-degree.) Define the edge out-boundary $\vec{\partial} S$ of a set $S\subset V$ to be the set of arrows coming out of it. It is not hard to prove (using the above) that there is a set $S'\subset V$ such that $G|_{S'}$ is connected and $\vec{\partial} S$ has $\geq (n/4+2)/3$ elements. (In fact, for that, we do not need to assume that $G'$ is strongly connected - we only need to assume that the in-degree of every vertex is positive, together with the assumptions on $G$.)

Can we obtain something stronger, with the right assumptions? Say the number $N$ of arrows coming in and out of vertices that have degree $\geq 3$ in $G$ is quite large - much larger than $n$. Can one really not do better than $\geq (n/4+2)/3$?

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 n/4+2$ elements.

(Proof: construct a spanning tree with $\geq 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?).)

Now draw some arrows between vertices of $G$ - i.e., define a directed multigraph $G'=(V,E')$ with the same set of vertices $V$ as $G$. Assume that $G'$ is strongly connected. (If it helps, assume as well that the out-degree of every vertex equals its in-degree.) Define the edge out-boundary $\vec{\partial} S$ of a set $S\subset V$ to be the set of arrows coming out of it. It is not hard to prove (using the above) that there is a set $S'\subset V$ such that $G|_{S'}$ is connected and $\vec{\partial} S$ has $\geq (n/4+2)/3$ elements. (In fact, for that, we do not need to assume that $G'$ is strongly connected - we only need to assume that the in-degree of every vertex is positive, together with the assumptions on $G$.)

Can we obtain something stronger, with the right assumptions? Say the number $N$ of arrows coming in and out of vertices that have degree >=3 in G is quite large - much larger than $n$. Can one really not do better than $\geq (n/4+2)/3$?

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 n/4+2$ elements.

(Proof: construct a spanning tree with $\geq 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?).)

Now draw some arrows between adjacent vertices of $G$ - i.e., define a directed multigraph $G'=(V,E')$ with the same set of vertices $V$ as $G$, and such that, if $(v,w)$ is an edge of $G'$, then $\{v,w\}$ is an edge of $G$. Assume that $G'$ is strongly connected. (If it helps, assume as well that the out-degree of every vertex equals its in-degree.) Define the edge out-boundary $\vec{\partial} S$ of a set $S\subset V$ to be the set of arrows coming out of it. It is not hard to prove (using the above) that there is a set $S'\subset V$ such that $G|_{S'}$ is connected and $\vec{\partial} S$ has $\geq (n/4+2)/3$ elements. (In fact, for that, we do not need to assume that $G'$ is strongly connected - we only need to assume that the in-degree of every vertex is positive, together with the assumptions on $G$.)

Can we obtain something stronger, with the right assumptions? Say the number $N$ of arrows coming in and out of vertices that have degree >=3 in G is quite large - much larger than $n$. Can one really not do better than $\geq (n/4+2)/3$?