... без изолированных вершин.
Другими словами, нужно доказать, что рёбра 3-регулярного графа можно покрасить в два цвета так, чтобы из каждой вершины выходили рёбра обоих цветов.
Пытался решить, подвешивая граф за вершину. Но тут не видно ничего. Ещё задал эту задачу ДипСику.
Сначала он сказал, что рёбра любого графа можно ориентировать так, чтобы входящая и исходящая степени любой вершины отличались не более, чем на 1. Тогда покрасим все входящие в 1 цвет, а исходящие во 2 цвет
Вторая его попытка была более интересной. Он сказал, что по теореме Петерсона кубический граф без мостов содержит совершенное парасочетание. Его красим в один цвет, а всё остальное в другой. А так как в кубических графах мостов не бывает, то задача решена.
Но оказалось, что в кубических графах всё же бывают мосты, и бывают кубические графы, в которых нет совершенного парасочетания
цвета так, что рёбра одного цвета не имеют общих концов).