Олимпиадные задачи из источника «1999 год» для 11 класса - сложность 2-3 с решениями

Раскраска вершин графа называется <i>правильной</i>, если вершины одного цвета не соединены ребром. Некоторый граф правильно раскрашен в <i>k</i> цветов, причём его нельзя правильно раскрасить в меньшее число цветов. Докажите, что в этом графе существует путь, вдоль которого встречаются вершины всех <i>k</i> цветов ровно по одному разу.

<i>a, b, c</i> – стороны треугольника. Докажите неравенство   <img align="middle" src="/storage/problem-media/105065/problem_105065_img_2.gif">