Решение #2:  

За решението ще приемем, че графът не е двуделен, защото ако е, сме готови - оцветяваме го с 2 цвята.

Ще използваме следното наблюдение - всеки граф от описания вид има поне един връх от степен <= 2. Има различни начини по които може да се докаже.

Нека решим задачата с индукция. Нека V е множеството от върхове, а връх u е върхът с най-малка степен. От горното наблюдение знаем, че deg(u) <= 2. Нека оцветим по индукция графа G'(V \ {u}, E). Сега ще оцветим u. Тъй като знаем, че броя съседни е <= 2, има най-много 2 изполвани цвята в съседитe му, а ние можем да използваме 3 цвята => col(u) = MEX (adj_colors(u)) е валидна конструкция.

Така задачата се свежда до намиране на реда на върховете, които ще махаме и до факта че всеки граф от описания начин може да се оцвети с 3 цвята.






Решение #3:

Това решения използва разделяй и владей, но за да го използваме/измислим трябва да сме забелязали, че 3 цвята са винаги достатъчни. 

Нека solve(L, R) оцветява всички върхове от L до R. Основната ни едея е да намерим връзка, която разделя [L; R] на два "сравнително" равни интервала, след което да оцветим всеки от тях поотделно и накрая да слеем оцветяванията. 

1) намирането на разделящата връзката може да се направи линейно, тъй като дълбочината на разделяй и владея ще е log M, та амортизирана сложност е M log M.
2) Оцветяването на двете части става като викнем solve(PART_1) и solve(PART_2). Трябва да забележим, че върховете в двете части ще са съседни, но може да има интервал от рода на [n-2, n-1, n, 1, 2], тъй като n и 1 също са съседни. Също трябва да итерираме връзките по такъв начин, че да не ги повтаряме в различните рекурсии на едно и също ниво.
3) Сливането става като направим мапинг на цветовете в едно от частите, използвайки другата. Отново е една идея по-сложно за имплементиране.