6. Какое минимальное число красок потребуется для правильной окраски граней усечённого: а) тетраэдра; б) куба; в) октаэдра; г) икосаэдра; д) додекаэдра (рис. 18.7)?

Соседними считаем грани, имеющие общее ребро.

1. а) Тетраэдр — 4 краски. Каждая его грань соседствует с тремя остальными, поэтому всем четырём нужны разные краски.
2. б) Куб — 3 краски. Противоположные грани можно окрасить попарно одной краской; грани каждой пары не соседствуют. Трёх красок необходимо, поскольку у вершины куба сходятся три попарно соседние грани.
3. в) Октаэдр — 2 краски. Его грани можно чередовать двумя красками: граф соседства граней октаэдра является графом куба, который можно раскрасить в два цвета.
4. г) Икосаэдр — 3 краски. Граф соседства его граней является графом додекаэдра: он содержит нечётные циклы, поэтому двух красок недостаточно, но допускает раскраску тремя.
5. д) Додекаэдр — 4 краски. Граф соседства его граней является графом икосаэдра. Пять граней, соседствующих с одной выбранной гранью, образуют цикл нечётной длины; для их раскраски нужны как минимум три краски, а самой выбранной грани — ещё одна. Четырёх красок достаточно.

Ответ: а) 4; б) 3; в) 2; г) 3; д) 4 краски.