Олимпиада Туймаада по математике. Старшая лига. 2016 год

Дан связный граф. Докажите, что можно раскрасить все его вершины в синий и зелёный цвета и отметить в нём некоторые рёбра так, чтобы каждые две вершины были соединены путём из отмеченных рёбер, каждое отмеченное ребро соединяло вершины разных цветов и никакие две зелёные вершины не были соединены ребром исходного графа. ( В. Дольников )