## 30. New City

The New City is built in the form of 12 rectangular blocks of houses, separated by streets; there is a mailbox at each corner of a block and at each street intersection. The blocks touch each other with entire sides or have only one common corner.

![](https://cdn.mathpix.com/cropped/2024_05_21_fe999c0fe2ad81fc5164g-040.jpg?height=665&width=1334&top_left_y=661&top_left_x=361)

Suppose there are a total of 37 street segments that define the city blocks, i.e., 37 intervals between mailboxes. How many mailboxes are there in this city?
30. Let's examine two arbitrarily chosen possible configurations of 12 blocks.
![](https://cdn.mathpix.com/cropped/2024_05_21_fe999c0fe2ad81fc5164g-135.jpg?height=404&width=1152&top_left_y=1708&top_left_x=456)

We can observe that for each of these configurations, the number of mailboxes is 26. In fact, this number does not depend on the details of the city plan. Euler ${ }^{1}$ proved the following theorem g $^{2}$.[^25]

If the number of vertices, edges, and faces (i.e., regions bounded by edges) of any planar graph are $b, p$, and $r$ respectively, then

$$
b-p+r=2
$$

In our case, $b$ is the number of vertices, i.e., mailboxes, $p=27$ is the number of edges, i.e., street segments, and $r=12+1=13$ is the number of faces, i.e., the number of blocks plus 1, which is due to the presence of the external (infinite) face. Thus, we have

$$
b-37+13=2 \text {, i.e., } b=26 .
$$