# 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.

• I am confused why this is not false for the disjoint union of $K_4$'s. Jul 28 at 7:33
• Ah, forgot to add that $\Gamma$ is connected. Jul 28 at 11:06
• Doesn't "graph" mean "finite graph"? -- it wouldn't hurt to mention finiteness ($|V|<\infty$). Aug 1 at 1:27
• Sure, finite... Aug 1 at 3:53
• If we allowed multiple edges, it would be easy to construct a counterexample. I wonder whether that can help us construct a true counterexample (to statement A or statement B)? Aug 1 at 7:50

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.

• I didn't get why the number of edges of $G_k$ is $\frac{k+3}{2} 2^{2^{k+1}}$. To me, it looks more like $2^{2^k-1}+2^{2^k-1} \cdot 2^{2^{k-1}-1} + \dotsc$, whose dominant term is $2^{2^k-1} \cdot 2^{2^{k-1}-1} \dotsb 2^{2^2-1} |G_1| = 2^{2^{k+1}-k}$. Aug 3 at 4:04
• Redoing the calculations I still end up with the same numbers; I have now added the induction to my answer so you can tell me where you think it goes wrong. Aug 3 at 6:47
• Ah, I think you are right. Thanks! Aug 4 at 9:10

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$$.

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$$.

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!

• $N$ is the number of edges of $\Gamma$, not its number of vertices. Also, don't forget about the connectedness condition! Jul 27 at 15:58
• Oh sorry, I read too fast! It seemed suspiciously easy. I’ll think more! Jul 27 at 15:59

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.