Fomin S.B.
In the kingdom, there are eight cities. The king wants to build such a road system that from each city it would be possible to reach any other city by passing through no more than one intermediate city, and so that no more than $k$ roads lead out of each city. For what values of $k$ is this possible?
If $k=2$, then from city A, one can "in one move" reach no more than two cities, and from them "in the next move" - no more than four. In total, from A, one can reach no more than six cities, but seven are needed. For $k=3$, arrange the cities at the vertices of a regular octagon, and place the roads along all sides and major diagonals.

## Answer

For $k>2$.