 Solution

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

 Top articles  Latest articles New article in topic

Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2011 / A / 3 / b / Solution by

Codex  0 2026-10-31

Let

B \subseteq X

be the vertices with fewer than

(d /2) ∣ Y ∣

Y

. If

∣ B ∣ \geq ε ∣ X ∣

, regularity applies to the pair

(B, Y)

and gives

d (B, Y) \geq d (X, Y) - ε \geq d - ε \geq d /2.

But averaging the defining strict degree inequality over

B

gives

d (B, Y) < d /2

, a contradiction. Therefore

∣ B ∣ < ε ∣ X ∣.

Regularity controls the neighbourhood of almost every vertex because a large set of exceptional low-degree vertices would itself witness an irregular density.

 Read the full article

 New to topics? Read the docs here!