Five cities are to be connected by a railway network consisting of four straight segments so that it is possible to travel from any city to any other. (No three cities lie on the same straight line. The segments may intersect.) How many such railway networks are possible?
I. solution. Let's denote the cities by $A, B, C, D$ and $E$. The four segments have $4 \cdot 2=8$ endpoints. Each endpoint belongs to one of the cities, so there will be a city from which more than one railway segment starts. Accordingly, we distinguish three cases.

![](https://cdn.mathpix.com/cropped/2024_05_02_806d5289c0cc58e18fd6g-1.jpg?height=385&width=333&top_left_y=306&top_left_x=880)

1. Figure
2. From one city - in our diagram, this city is $A$ - four railway lines start. Since $A$ can be any of the cities, there are 5 such railway networks possible.
3. From one city - in the 2nd diagram, this is $A$ - three railway lines start.

![](https://cdn.mathpix.com/cropped/2024_05_02_806d5289c0cc58e18fd6g-1.jpg?height=439&width=336&top_left_y=954&top_left_x=881)

The three endpoints of the three segments from $E$ that are different from $A$ are connected to the fifth city, so there will be a city from which two segments start. The city from which 3 railway lines start can be chosen in 5 ways from the 5 cities, the city from which 2 lines start in 4 ways, and the remaining 3 can be chosen in 3 ways to be the "fifth" city mentioned in the previous sentence. This is $5 \cdot 4 \cdot 3=60$ cases.

3. From each city, at most 2 railway lines start. We have drawn this case in the 3rd diagram.

![](https://cdn.mathpix.com/cropped/2024_05_02_806d5289c0cc58e18fd6g-1.jpg?height=369&width=355&top_left_y=1694&top_left_x=863)

3. Figure

If we traverse the segments of such a railway network in a connected manner, we will encounter the five cities in the order of one of their permutations. The number of these is 5! = 120, but from the perspective of the railway network, for example, the networks $A B C D E$ and $E D C B A$ are identical; therefore, the number of different possibilities is $\frac{1}{2} \cdot 5!=60$.

In total, we have found $5+60+60=125$ railway networks.

Remark. The problem (and the solution) can also be formulated using the terminology of graph theory. Our problem means how many different 5-vertex trees are possible, or generally: how many different $n$-vertex trees exist.

II. solution. The general solution to the problem can be found on pages 318-319 of István Reiman's book "A geometria és határterületei" (Geometry and its boundary areas). According to the so-called Cayley formula, the number of $n$-vertex trees is $n^{n-2}$.