Chromatic Bound for a Graph
Source: 239 2015 S P3
May 14, 2020
graphColoringcombinatorics
Problem Statement
The edges of a graph are coloured in two colours. Such that for each colour all the connected components of this graph formed by edges of this colour contains at most vertices. Prove there exists a proper colouring for the vertices of this graph with colours.