A surveillance service is to be installed in a park in the form of a network of stations. The stations must be connected by telephone lines so that any of the stations can communicate with all the others, either by a direct connection or through at most one other station. Each station can be directly connected by a cable to at most 3 other stations.

The diagram shows an example of such a network connecting 7 stations. What is the maximum number of stations that can be connected in this way?

![](https://cdn.mathpix.com/cropped/2024_05_01_2b4d243432ecfddb5212g-1.jpg?height=317&width=323&top_left_y=1338&top_left_x=1409)
The example shows that we can connect at least 7 stations under the proposed conditions. We start with a particular station, and think of it as the base of the network. It can be connected to 1, 2, or 3 stations as shown in the diagram.

![](https://cdn.mathpix.com/cropped/2024_05_01_2b4d243432ecfddb5212g-3.jpg?height=274&width=328&top_left_y=1439&top_left_x=864)

Now, stations A, B, and C still have two unused lines, so they can be connected to two other stations as follows:

![](https://cdn.mathpix.com/cropped/2024_05_01_2b4d243432ecfddb5212g-3.jpg?height=469&width=525&top_left_y=2007&top_left_x=774)

Now, it is impossible to add more stations because any additional one would not be able to connect to the base while satisfying the conditions of the problem. This shows that we cannot have more than 10 stations. Let's now check if we can build the network with these 10 stations. Observe in the diagram above that only the Base is connected to all other stations (either directly or via a connection through another station). The stations at the ends still have two unused lines, and now we will use them to "close" the network; see the following diagram.

![](https://cdn.mathpix.com/cropped/2024_05_01_2b4d243432ecfddb5212g-4.jpg?height=628&width=711&top_left_y=1062&top_left_x=730)