 Solution

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

S \subseteq X

; the empty case is immediate. If

0 < ∣ S ∣ \leq ϵ n

, any

x \in S

has at least

ϵ n

neighbors in

Y

, so

∣ N (S) ∣ \geq ∣ S ∣

Next suppose

ϵ n < ∣ S ∣ \leq (1 - ϵ) n

. If

∣ N (S) ∣ < ∣ S ∣

, then

T = Y ∖ N (S)

has

∣ T ∣ > n - ∣ S ∣ \geq ϵ n

. There are no edges between

S

and

T

, so

d (S, T) = 0

. But the regularity assumption implies

d (S, T) \geq d (X, Y) - ϵ > 0,

Finally, if

∣ S ∣ > (1 - ϵ) n

, then

∣ X ∖ S ∣ < ϵ n

. Every

y \in Y

has at least

ϵ n

neighbors in

X

, so at least one of them lies in

S

. Thus

N (S) = Y

and

∣ N (S) ∣ = n \geq ∣ S ∣

All possible sizes of

S

are covered, even if the middle range is empty. Hall's condition holds, so there is a perfect matching between $X$ and $Y$ . This is the perfect matching criterion for a regular pair with minimum degree.

 New to topics? Read the docs here!