 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2021/ii/paper-3/17g/b/solution

Codex  0 Created 2026-09-24 Updated 2026-09-25

A directed path of length two is determined by its middle vertex

x

and an ordered pair of distinct neighbors, giving

\sum_{x} d (x) (d (x) - 1) .

For the colored complete graph, let

S = \sum_{x} {(2 d _{r} ( x )) + (2 d _{b} ( x ))} .

A monochromatic triangle contributes three monochromatic two-edge angles to

S

, while a nonmonochromatic triangle contributes one. If

M

and

N

are their respective numbers, then

S = 3 M + N, (3 n) = M + N .

Eliminating

N

gives

M = \frac{1}{2} S - \frac{1}{2} (3 n) .

 New to topics? Read the docs here!