72. Railway Network (I). There are five cities; no three of them lie on the same straight line. These cities need to be connected by a railway network consisting of four straight roads; at that, railway lines can be built one over another on viaducts.

How many such different railway networks exist?
72. There can exist three types of railway networks, as shown in Fig. 149.
1) In the first case, each city can be a node where four lines converge, so there will be five different networks of this kind.
2) In the second case, a city that will be a node where three lines converge can be connected to three other cities in four ways (the number of combinations of four elements taken three at a time), and the fifth city in each of these cases can be connected to each of these three cities, so there are a total of $4 \cdot 3=12$ possible connections. Since any of the five cities can be the node, the total number of different networks of this kind will be $5 \cdot 12=60$.
3) In the third case, in the network connecting the cities, the order of the cities can be changed arbitrarily, so we will have as many networks as there are permutations of five elements, i.e., $5!=120$. But each permutation and its reverse permutation define the same network, so the number of different networks will be $120: 2=60$.

In total, there are $5+60+60=125$ networks.

![](https://cdn.mathpix.com/cropped/2024_05_21_5d77f4829f88503a49eag-146.jpg?height=320&width=1104&top_left_y=818&top_left_x=478)

Fig. 149.