Областная олимпиада по математике, 2017 год, 10 класс

В компьютерной сети 2017 компьютеров. Любые два компьютера соединены кабелем. Из-за перегрузок в сети периодически перегорает один из кабелей в некоторой части сети, образующей цикл из четного числа компьютеров. Может ли через какое-то время остаться ровно 2016 целых кабелей, если ни один из перегоревших кабелей не ремонтируется?

Комментарий/решение

Решение. Предположим это возможно. Так как разрывы происходят только внутри некоторых циклов, то связность графа при каждом перегорании не нарушается. Это означает, что в конце мы получим дерево на 2017 вершинах, любое дерево является двудольным графом.

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