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

Рассмотрим граф, вершины которого олицетворяют комнаты замка, а ребро присутствует между двумя вершинами, если соответствующие им комнаты являются соседними. Из условия о том, что из каждой комнаты можно попасть в любую другую следует, что граф связен. Тогда рёбер в нём хотя бы уменьшенное на число вершин, то есть хотя бы Заметим, что периметр замка — утроенное число вершин (суммарное число сторон комнат) минус удвоенное число рёбер (стороны, которые не должны учитываться в периметре, но нами посчитаны соответственно для двух комнат). Эта величина максимум равенство достигается при треугольничках в ряд (последовательно повёрнутые в разные стороны).