Считаем рёбра

(a) Рассмотрим граф, в котором дети это вершины. Будем проводить ребро, если дети дружат. По условию все вершины имеют степень 2, значит, в графе 30 рёбер. Будем выбирать произвольное ребро, выкидывать вершины на его концах и все рёбра, исходящие из этих вершин. Так мы удалим не более 3 рёбер (поскольку степени вершин не превосходят 2, а одно из рёбер у этих вершин общее). Значит, если проделать такой процесс 9 раз, останется хотя бы 3 ребра, и удастся сделать десятый шаг. Составим пары для дежурств из учеников, соответствующих концам выбранных ребер. Тогда дежурят только друзья, и никто не дежурит дважды, поскольку мы сразу же удаляем вершины. Таким образом, мы выбрали 10 пар.

(b) Пусть граф состоит из 10 треугольников: компонент связности размера 3, каждая из которых является полным графом. Тогда степень каждой вершины равна 2, при этом дежурить должны дети из одного треугольника, каждый треугольник даёт только по одному дежурству (поскольку все дежурят не более одного раза), но треугольников всего 10, значит, 11 дежурств провести не получится.