MathDB

5

Part of 2022 South Africa National Olympiad

Problems(1)

SAMO 2022 Problem 5 - Graph colouring problem

Source: South African Mathematics Olympiad 2022, Problem 5

8/11/2022
Let n≥3n \geq 3 be an integer, and consider a set of nn points in three-dimensional space such that:
[*] every two distinct points are connected by a string which is either red, green, blue, or yellow; [*] for every three distinct points, if the three strings between them are not all of the same colour, then they are of three different colours; [*] not all the strings have the same colour.
Find the maximum possible value of nn.
combinatoricsgraph theoryGraph coloring