Problem

Source: Bulgaria National Olympiad 2020

Tags: combinatorics, Graph coloring, graph theory



There are $n$ points in the plane, some of which are connected by segments. Some of the segments are colored in white, while the others are colored black in such a way that there exist a completely white as well as a completely black closed broken line of segments, each of them passing through every one of the $n$ points exactly once.

HIDE: It is known that the segments $AB$ and $BC$ are white. Prove that it is possible to recolor the segments in red and blue in such a way that $AB$ and $BC$ are recolored as red, not all of which segments are recolored red meaning that recoloring every white as red and every black as blue is not acceptable

, and that there exist a completely red as well as a completely blue closed broken line of segments, each of them passing through every one of the $n$ points exactly once.