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

Table of contents
- Solution b

Solution

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

If

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

.

 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