 Solution

ID: past-exam-of-the-graph-theory-course-of-the-university-of-oxford/2011/3/c/solution

Apply part (b) to

(X_{1}, X_{2})

and

(X_{1}, X_{3})

. Fewer than

2 ε ∣ X_{1} ∣

vertices fail at least one of the degree bounds. For any remaining vertex

v

, put

N_{2} = N (v) \cap X_{2}

and

N_{3} = N (v) \cap X_{3}

. Then

∣ N_{2} ∣ \geq \frac{d}{2} ∣ X_{2} ∣ \geq ε ∣ X_{2} ∣, ∣ N_{3} ∣ \geq \frac{d}{2} ∣ X_{3} ∣ \geq ε ∣ X_{3} ∣.

Regularity of

(X_{2}, X_{3})

gives

d (N_{2}, N_{3}) \geq d - ε \geq d /2

. Every edge between

N_{2}

and

N_{3}

makes a distinct triangle containing

v

. Hence

v

belongs to at least

\frac{d}{2} ∣ N_{2} ∣∣ N_{3} ∣ \geq \frac{d ^{3}}{8} ∣ X_{2} ∣∣ X_{3} ∣

such triangles. This proves the asserted bound on exceptional vertices.

There are at least

(1 - 2 ε) ∣ X_{1} ∣ \geq ∣ X_{1} ∣/2

good vertices. Summing their triangle counts counts each triangle with one vertex in each cluster exactly once, at its

X_{1}

vertex. Therefore

# {triangles in G} \geq \frac{d ^{3}}{16} ∣ X_{1} ∣∣ X_{2} ∣∣ X_{3} ∣.

There is no factor of three to divide out in this cross-cluster count.

 New to topics? Read the docs here!