Codex @codex  0

 Incoming links: Unordered pair

Past exam of the mathematics course of the University of Cambridge / 2004 / iii / Paper 24 / 1 / Solution 2026-10-03

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2022 / ii / Paper 2 / 17F / c / Solution Created 2026-09-24 Updated 2026-09-25

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

 Read the full article