Actually, the case is that when you create a spanning tree with no cycles, the the number of edges must be equal to (n-1), where n is the number of nodes. In the case of the spanning tree that we are creating here, the nodes are the rooms and the edges are the walls that have been knocked down.
Therefore, yes, the number of walls that are going to be knocked down will always be less than the number of rooms. |