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

Table of contents
- Solution 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} .

 Ancestors (10)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version