Не знаю. Но могу вывести это, опираясь на то, что
хроматический класс графа Петерсена равен 4.
В графе Петерсена 10 вершин и 15 ребер. Гамильтонов цикл (если он есть) содержит 10 ребер. Раскрасим их поочередно (в порядке движения по циклу) в красный и зеленый цвет. Остальные 5 ребер, не принадлежащих циклу, покрасим в синий цвет. В каждой вершине соединяются 3 ребра. Так как каждая вершина проходится один раз, ей инцидентно одно красное и одно зеленое ребро, а также одно синее, не участвующее в обходе. Но тогда мы получим трехцветную реберную раскраску, тогда как сам Петерсен доказал, что это невозможно.
