ВСОШ 2026, региональный этап, 11 класс, задача 5
( баллов) Некоторые рёбра выпуклого многогранника удалось покрасить в красный цвет так, что в каждую вершину входит ровно два красных ребра, причём эти рёбра лежат в одной грани. Кроме того, в каждой грани оказалось не более двух красных рёбер. Сколько вершин может быть в таком многограннике?
Ответ
Ответ. Ответ: любое чётное число вершин, большее .
Решение. Поскольку из каждой вершины исходит ровно два красных ребра, то красные рёбра образуют несколько непересекающихся циклических маршрутов по вершинам многогранника. Рассмотрим один такой цикл из красных рёбер, он делит поверхность многогранника на две части, покрасим одну из таких частей в синий цвет, другую в зелёный. Пусть — одна из вершин циклического маршрута. Исходящие из неё красные рёбра лежат в одной грани по условию задачи. Покрасим вершину в тот цвет, в который покрашена эта грань. Таким образом мы получим, что в циклическом маршруте синие и зелёные вершины чередуются, поэтому вершин в нем чётное число. Следовательно, и общее количество вершин в многограннике чётно.
Теперь приведём пример для чётного числа вершин. Для вершин подойдет тетраэдр , в котором красным покрашены ребра , , , . Пусть . Рассмотрим правильную -угольную призму и соответствующую -вершинную антипризму, образованную вершинами , где , и вершинами , где . Под условие подойдёт покраска в красный цвет рёбер, по которым граничат «боковые» треугольные грани: , , , . Таким образом, в каждой треугольной грани будет окрашено два ребра, а в двух -угольных гранях не будет красных рёбер.