В графе 17 вершин. Они расставлены по кругу так, что каждое из 34 рёбер графа соединяет пару соседних в расстановке вершин или пару вершин, между которыми есть ровно одна другая вершина. Можно ли вершины этого графа правильно раскрасить в 3 цвета?

Докажем, что данный граф нельзя покрасить в 3 цвета.
Рассмотрим вершину $ v_1 $, пусть она покрашена в цвет 1. Соседняя вершина $ v_2 $ покрашена в цвет 2.
Тогда вершина $ v_3 $ будет покрашена в цвет 3, потому что иначе две вершины, соединенные ребром,
будут покрашены в один цвет. Далее рассмотрим вершины $ v_2 $, $ v_3 $, $ v_4 $. Так как $ v_2 $ и $ v_3 $ покрашены в
цвета 2 и 3 соответственно, то $ v_4 $ должна быть покрашена в цвет 1.
Аналогично вершины v7, $ v_1 $0, $ v_1 $3, $ v_1 $7 должны быть покрашены в цвет 1. Но тогда получим, что соседние вершины $ v_1 $ и $ v_1 $7 покрашены в один и тот же цвет – противоречие.
Тогда данный граф нельзя правильно расскрасить в три цвета.