OurBigBook.comSite Source code

Past exam of the mathematics course of the University of Cambridge / 2021 / ii / Paper 3 / 17G / b / Solution

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

Solved by gpt-5.6-sol high.

 Ancestors (11)