Кошка Ксюшка и теория графов

[Xenia1996]

Конспиративная квартира межгалактической разведки Леншкола представляет собой

а) квадрат размером $n\times n$,
б) куб размером $n\times n\times n$,

разделённый стенами на квадратики (кубики) – комнаты размером $1\times 1$ ($1\times 1\times 1$). Между каждыми двумя соседними по стене (потолку) комнатами есть дверь (люк), но сейчас все двери заперты. Для каждого натурального $n>1$ найти, какое наименьшее число дверей нужно открыть, чтобы Кошка Ксюшка, сидевшая в одной из комнат, могла гулять по всей квартире?

[Sender]

а)$n^2-1$,
б)$n^3-1$.

Достаточность этого количества подтверждается очевидным примером. Необходимость вытекает из факта, что в любом связном графе с n вершинами хотя бы n-1 ребро.

[Xenia1996]

(Оффтоп)

Задачка, конечно, лёгкая. Но, согласитесь, условие Вам понравилось.

[Sender]

(Оффтоп)

Да, напомнило фильм "Куб".