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

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

Комментарий/решение

Индукцию по количеству вершин $n$. Очевидно что для $n=2,3$ это верно. Предположим, что это верно для $n-1$. Удалим одну вершину и для оставшихся $n-1$ вершин это верно. Теперь добавим нашу вершину $v_n$. Если все её соседи по ребру раскрашены в синий тогда красим $v_n$ в зеленый и отмечаем все вершины которые из неё исходят. Если же есть сосед окрашенный в зеленый тогда красим её в зеленый и отмечаем именно общие ребро с зелеными вершинами. $\blacksquare$