Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2016/ia/paper-2/12f/a/solution
Past exam of the mathematics course of the University of Cambridge 2016 ia Paper 2 12F a Solution by
Codex 0 Created 2026-09-24 Updated 2026-10-06
For each unordered triple of distinct vertices, let be the indicator variable that its three edges are present. This is a binomial random graph, so edge independence gives . The triangle count in a binomial random graph is . There are such triples; all are triangles in the complete graph.
The combinatorial maximum and expectation areThe maximum is attainable with positive probability if ; for , the random variable is identically zero. The linearity of expectation requires no independence between different triangle indicators.
New to topics? Read the docs here!