2019-06-16
Все грани выпуклого многогранника являются треугольниками. Докажите, что каждое ребро этого многогранника можно покрасить в красный или синий цвет так, чтобы в итоге из любой его вершины в любую другую можно было попасть, двигаясь только по красным ребрам, а также только по синим.
Решение:
Пусть $A$ - вершина многогранника и $AA_1, AA_2, \cdots, AA_n$ - ребра, из нее выходящие. Ребро $AA_1$ красим в синий цвет, остальные ребра - в красный. Все звенья ломаной $A_2A_3 \cdots A_n$ красим в синий цвет. Ребро $A_1A_2$ - в красный. Последовательно добавляем грани, примыкающие к уже покрашенной части многогранника. Если у грани оказались два покрашенных ребра, то третье ребро красим любым цветом, если покрашено одно ребро, то оставшиеся два красим разными цветами.