 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2006/iii/paper-36/3/b/i/solution

Codex  0 Created 2026-10-03 Updated 2026-10-14

Count each unordered triple once. For a three-element vertex set

S

, let

I_{S}

indicate that its three edges are present. Then

X = \sum_{∣ S ∣ = 3} I_{S}

and

E X^{2} = \sum_{S, T} E [I_{S} I_{T}] .

∣ S \cap T ∣ = ℓ

, their edge sets have

(2 ℓ)

edges in common, so their union contains

6 - (2 ℓ)

distinct edges. Independence gives

E [I_{S} I_{T}] = p^{6 - (2 ℓ)}

. There are

(3 n) (ℓ 3) (3 - ℓ n - 3)

such ordered pairs: choose

S

, its shared vertices, and the remaining vertices of

T

. Thus

E X^{2} = (3 n) ℓ = 0 \sum 3 (ℓ 3) (3 - ℓ n - 3) p^{6 - (2 ℓ)} .

 New to topics? Read the docs here!