MathDB
Colouring a complete graph

Source: Baltic Way 2017, Problem 7

November 26, 2017
combinatoricsGraph coloringgraph theory

Problem Statement

Each edge of a complete graph on 3030 vertices is coloured either red or blue. It is allowed to choose a non-monochromatic triangle and change the colour of the two edges of the same colour to make the triangle monochromatic. Prove that by using this operation repeatedly it is possible to make the entire graph monochromatic. (A complete graph is a graph where any two vertices are connected by an edge.)