Color edges of a graph with red or blue
Source: 2017 Thailand October Camp 1.8
February 25, 2022
Graph coloringcombinatoricsgraph
Problem Statement
There are vertices and edges in a graph. Each edge is colored either red or blue. In each year, we are allowed to choose a vertex and flip the color of all edges incident to it. Prove that there is a way to color the edges (initially) so that they will never all have the same color