Данное утверждение верно для несвязного графа, если оно верно для связного графа, так как раскраска рёбер одной связной компоненты никак не влияет на раскраску рёбер другой связной компоненты.
Связный граф, все вершины которого имеют степень 4, является эйлеровым, так как 4 - чётное число. То есть в таком графе существует эйлеров цикл, проходящий по одному разу через все рёбра графа. Длина этого цикла - чётная потому, что она равна 4n/2 = 2n, где n - количество вершин графа.
Раскрасим рёбра этого цикла в два цвета, чередуя их. В результате получим раскраску, в которой любые два последовательных ребра имеют разные цвета.
Любая вершина эйлерова графа с вершинами степени 4 инцидентна двум парам последовательных рёбер эйлерова цикла. В обеих парах оба ребра имеют разные цвета. То есть из 4 ребер любой вершины два будут одного цвета и два - другого. Что и требовалось доказать.
