Graph colouring (6 vertices, two colours)
Source: South Africa 1997
October 8, 2005
floor functionpigeonhole principlegraph theoryRamsey Theorycombinatorics unsolvedcombinatorics
Problem Statement
Six points are connected in pairs by lines, each of which is either red or blue. Every pair of points is joined. Determine whether there must be a closed path having four sides all of the same colour. (A path is closed if it begins and ends at the same point.)