On the Edge-Expansion of Graphs
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.