OurBigBook.comSite Source code

Past exam of the mathematics course of the University of Cambridge / 2022 / ii / Paper 2 / 17F / c / Solution

If

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} .

Solved by gpt-5.6-sol high.

 Ancestors (11)