4. The city has a square grid with $m$ horizontal and $n$ vertical streets (diagram on the right). What is the minimum length of the part of the grid that needs to be asphalted so that from any intersection to any other intersection, one can reach by an asphalted road?
Solution. In the city, there are $m n$ intersections. Let's call the part of the street between two adjacent intersections an alley. To start from one intersection and pass through each of the remaining $m n-1$ intersections by moving along the paved part of the network, at least $m n-1$ alleys must be paved (we reach each subsequent intersection via a new alley). In the diagram on the right, a network is shown where

![](https://cdn.mathpix.com/cropped/2024_06_05_72b79cc38cc70f646757g-08.jpg?height=634&width=348&top_left_y=576&top_left_x=1132)

$$
n(m-1)+n-1=m n-1
$$

alleys are paved, and any two intersections are connected by a paved path.

## Junior Olympiad