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