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

Table of contents
- Solution 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) .

 Ancestors (10)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version