6–7. а) На рисунке изображён план подвала из 10 комнат. Можно ли пройти через все двери всех комнат, запирая каждый раз ту дверь, через которую вы проходите? С какой комнаты надо начинать движение?

Представим каждую комнату вершиной, а каждую дверь — ребром между комнатами. Чтобы пройти через каждую дверь ровно один раз, нужен эйлеров путь: граф должен быть связным и иметь ровно две вершины нечётной степени; начать нужно в одной из них.

По плану степени комнат таковы: у комнат 1, 4, 6 и 10 — по 3 двери; у комнат 2, 3, 5, 7, 8 и 9 — по 2 двери. Значит, нечётную степень имеют четыре комнаты: 1, 4, 6 и 10.

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

Ответ: пройти через все двери нельзя; комнаты, с которой можно начать такой маршрут, нет.