Combinatorics, Probability and Computing

On the Edge-Expansion of Graphs

a1 Department of Mathematics, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, Israel (e-mail:


It is shown that if n>n0(d) then any d-regular graph G=(V, E) on n vertices contains a set of u=[lfloor O: left floor]n/2[rfloor C: right floor] vertices which is joined by at most (d/2−c[surd radical]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.

(Received December 24 1995)
(Revised May 31 1996)


1 Research supported in part by a USA Israeli BSF grant and by the Fund for Basic Research administered by the Israel Academy of Sciences.