 Solution

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

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

G

contains no

K_{3, 2}

, every pair of vertices has at most two common neighbours. Double-counting a vertex together with an unordered pair of its neighbours gives

\sum_{v} (2 d ( v )) \leq 2 (2 n) .

Consequently

\sum_{v} d (v)^{2} \leq 2 n (n - 1) + 2 e .

By Cauchy--Schwarz,

\frac{4 e ^{2}}{n} \leq 2 n (n - 1) + 2 e .

This quadratic inequality implies

e < c n^{3/2}

for an absolute constant

c

; for example

c = 2

works for every

n \geq 1

. Thus

ex (n, K_{3, 2}) < 2 n^{3/2} .

 New to topics? Read the docs here!