It is shown that if n > n 0 ( d ) then any d -regular graph G =( V , E ) on n vertices contains a set of u =[lfloor ] n /2[rfloor ] vertices which is joined by at most ( d /2− c √ d ) u edges to the rest of the graph, where c >0 is some absolute constant. This is tight, up to the value of c .
No takes yet. Share an insight, caveat, or question.
Noga Alon (1997) studied this question.
Synapse has enriched 3 closely related papers on similar clinical questions. Consider them for comparative context: