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.

  • 2
    $\begingroup$ I am confused why this is not false for the disjoint union of $K_4$'s. $\endgroup$ Jul 28 at 7:33
  • $\begingroup$ Ah, forgot to add that $\Gamma$ is connected. $\endgroup$ Jul 28 at 11:06
  • $\begingroup$ Doesn't "graph" mean "finite graph"? -- it wouldn't hurt to mention finiteness ($|V|<\infty$). $\endgroup$
    – Wlod AA
    Aug 1 at 1:27
  • $\begingroup$ Sure, finite... $\endgroup$ Aug 1 at 3:53
  • $\begingroup$ 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)? $\endgroup$ Aug 1 at 7:50

5 Answers 5


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

  • $\begingroup$ 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}$. $\endgroup$ Aug 3 at 4:04
  • $\begingroup$ 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. $\endgroup$ Aug 3 at 6:47
  • $\begingroup$ Ah, I think you are right. Thanks! $\endgroup$ 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!

  • $\begingroup$ $N$ is the number of edges of $\Gamma$, not its number of vertices. Also, don't forget about the connectedness condition! $\endgroup$ Jul 27 at 15:58
  • $\begingroup$ Oh sorry, I read too fast! It seemed suspiciously easy. I’ll think more! $\endgroup$
    – Richard
    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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.