 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2022/ii/paper-2/17f/b/solution

Codex  0 Created 2026-09-24 Updated 2026-09-25

Let

T

be the number of triangles. Each edge

uv

has at least

d (u) + d (v) - n

common neighbours, and summing common-neighbour counts over edges counts every triangle three times. Hence

3 T \geq uv \in E \sum (d (u) + d (v) - n) = v \sum d (v)^{2} - n e \geq \frac{4 e ^{2}}{n} - n e = e (\frac{4 e}{n} - n) .

e > (1 + δ) n^{2} /4

, this is greater than

δe n > δ n^{3} /4

. Therefore

T > \frac{δ}{12} n^{3},

so one may take

ε = δ /12

 New to topics? Read the docs here!