Оцветяване на граф

[Гост]

Даден е граф G с 3n върха, оцветени правилно в n цвята, по 3 върха от цвят (съседните върхове са разноцветни). Да се докаже, че можем да изберем по 1 връх от цвят, така че в индуцирания подграф от избрани върхове, всеки връх е от четна степен.

[drago]

Това не е вярно! Ето следния контрапример. Нека $C_1,C_2,\dots, C_n$ са $n$ взаимно непресичащи се множества, всяко с три елемента/върха. Свързваме всеки връх от $C_i$ със всеки връх от $C_{i+1}, i=1,2,\dots,n-1.$ Така получаваме графа $G$. Оцветяваме върховете съдържащи се в $C_i$ в цвета $c_i,i=1,2,\dots,n$ и получаваме правилно оцветяване на $G$. Очевидно е, че както и да изберем по един връх $v_i \in C_i,i=1,\dots,n$ върховете $v_1$ и $v_n$ ще имат степен $1$.

[Гост]

Да, контрапримера работи, но съм изпуснал в условието (съжалявам за което), че всеки връх от съседен на максимум два върха от всеки друг цвят.