Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2016/ia/paper-2/12f/a/solution

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 are
The 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!