Турниры в терминах графов и не только (считаем игры и очки)

Рассмотрим граф, в котором вершины это команды. Будем проводить ребро, если они ещё не сыграли. Легко проверить, что если вершин не больше 4, то турнир можно закончить за 3 дня. Теперь пусть вершин хотя бы 5. Пусть имеется вершина степени не меньше 3. Рассмотрим четверку: и три команды, с которыми она не играла. Добавим к этой четверке любую команду. Тогда в получившейся пятерке не выполняется условие на расстановку для вершины Значит, степень каждой вершины не превосходит 2.

Значит, граф разбивается на циклы и цепочки. За один день турнира из графа удаляется несколько рёбер так, что степень каждой вершины уменьшается не более, чем на 1. Цепочку мы можем удалить за 2 дня: возьмём рёбра через одно, а потом оставшиеся. Цикл можно удалить за 3 дня: уберём одно ребро и получим цепочку, которую разберём за 2 оставшихся дня.