Mice have built an underground house consisting of chambers and tunnels:

- each tunnel leads from one chamber to another (i.e., none are dead ends),
- from each chamber, exactly three tunnels lead to three different chambers,
- from each chamber, one can reach any other chamber via tunnels,
- the house has exactly one tunnel such that its collapse would divide the house into two separate parts.

What is the minimum number of chambers the mouse house could have? Sketch how the chambers could be connected.

(K. Jasenčáková)

Hint. Start with the critical tunnel.
We will denote cells with circles and tunnels with lines. We start with a critical tunnel, whose collapse divides the house into two separate parts. If we denote the cells at the ends of this tunnel as $A$ and $B$, then each cell belongs to exactly one of the following two groups:

a) cell $A$ and all cells that can be reached from it without using the tunnel $A B$,

b) cell $B$ and all cells that can be reached from it without using the tunnel $B A$.

This means that no cell from one group is connected by a tunnel to any cell from the other group. Now we will determine the minimum number of cells that can be in one group while satisfying the other conditions:

- For there to be three tunnels from cell $A$, there must be at least two more cells in group a), which we will denote as $C$ and $D$. However, three cells in the group are not enough - only $C$ and $D$ can be connected, and this would mean that only two tunnels lead from $C$ and $D$.
- Therefore, there must be at least one more cell in group a), which we will denote as $E$. However, four cells are still not enough - $E$ can only be connected to $C$ and $D$, and this would mean that only two tunnels lead from $E$.
- Therefore, there must be at least one more cell in group a), which we will denote as $F$. Five cells in one group are sufficient - the cells can be connected, for example, as follows:

![](https://cdn.mathpix.com/cropped/2024_04_17_5752a8a8cd9a6cffa1f9g-5.jpg?height=354&width=880&top_left_y=1756&top_left_x=591)

The house had at least 10 cells.