 Solution

ID: past-exam-of-the-graph-theory-and-probabilistic-combinatorics-course-of-the-university-of-oxford/2009/a/3/c/solution

Let

S \subseteq X

be the vertices with fewer than

d n /2

neighbours in

Y

. If

∣ S ∣ > ϵ n

, its density to all of

Y

is below

d /2

. But epsilon-uniformity applies to

(S, Y)

and requires

d (S, Y) > d (X, Y) - ϵ \geq d - ϵ > d /2,

a contradiction. Therefore $∣ S ∣ \leq ϵ n$ .

 New to topics? Read the docs here!