Связность и связные подграфы (клики)

Рассмотрим узлы, в которых соединяются стороны. Их всего Посчитаем, сколько узлов являются концами красных сторон. Заметим, что при добавлении каждой следующей стороны, кроме первой, добавляется новый такой узел. Действительно, если нового узла не появилось, то мы дважды покрасили какую-то сторону.

Теперь рассмотрим граф, в котором вершины — узлы, а ребром вершины соединены, лишь когда соответствующие узлы соединены красной стороной. В этом графе вершин и рёбер. Значит, он точно является связным и при этом не деревом, потому что в дереве было бы рёбер. То есть в нём есть цикл, что и требовалось.