Математикадан «Туймаада» олимпиадасы. Жоғары лига. 2016 жыл

Байланысқан граф берілсін. Әрбір екі төбе, белгіленген қабырғалар құрайтын жол арқылы байланысатындай және әрбір белгіленген қабырға, түстері әртүрлі төбелерді қосатындай және ешқандай екі жасыл түсті төбе осы графтың қабырғаларымен байланыспайтындай, осы графтың барлық төбелерін жасыл және көк түске бояп, ал кейбір қабырғаларды белгідеуге болатынын дәлелдеңіз. ( В. Дольников )

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

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