# Drawing lines on a map

This was a puzzle that appeared in an old math contest as well as an unrelated puzzle book.

Suppose we have a two-dimensional map with a lot of cities marked on it. For each city on the map, we draw a line segment to the city nearest to it (we assume that there is always a nearest city and that no two cities are exactly the same distance apart from any third city). Prove that no city will have more than five line segments connected to it.

I seem to remember that the proof involved triangles, but to this day don't know the whole proof.

-
Now, I'm not sure if this belongs more in Puzzling.SE with a math tag or in Math.SE with a puzzle tag, but I decided to put it here first. –  Joe Z. Jul 2 '14 at 23:17

I'll assume the cities lie on a flat plane, which seems to be the most reasonable interpretation of the question.

Let's assume (for contradiction) that we had a city which is connected to at least 6 other cities. First, note that this implies that no two cities lie on the same ray extending outwards from the central city which I'll label as $0$. Picking the closest of these six cities to be $1$ and label the cities counterclockwise starting from the ray $\vec{01}$ as $2,3, \ldots, 6$. Now $0$ and $1$ are connected since $1$ is closest to $0$. For cities $2, \ldots, 6$, the only way they can be connected to $0$ is by being closer to $0$ than they are to any other city. Here's a conceptual diagram:

First, let's deal with the two triangles $\Delta012$ and $\Delta 061$ which have city 1 as vertices. By construction, $d(0,1) < d(0,2)$, where $d(i,j)$ is the distance from $i$ to $j$. $1$ already has a segment connecting it to $0$ since it's the closest city to $0$. But for $2$, since it isn't the closest city to $0$, we need $0$ to be the closest city to it. So $d(0,2) < d(1,2)$. By transitivity, $d(0,1) < d(1,2)$, so the longest edge in $\Delta 012$ is $\overline{12}$. The same logic shows that the longest edge in $\Delta 061$ is $\overline{16}$.

Now, for $\Delta 023$, we know that $d(0,2) < d(2,3)$ and similarly $d(0,3) < d(2,3)$, both since $2$ and $3$ each have $0$ as their closest city. Hence, the longest edge of the triangle $\Delta 023$ is $\overline{23}$. We apply the same to $\Delta 034, \Delta 045, \Delta 056$ to show that the side opposite the angle at city $0$ is always the longest. This is thus true for all 6 triangles.

The law of sines tells us that either the largest side is opposite the largest angle, or else the "triangle" has a reflex angle (an angle greater than $180 ^\circ$). It's possible that $\angle 102$ is a reflex angle, but by construction it's not possible for either of the other angles to be a reflex angle, because we chose them to lie on rays going outwards from $0$, and there's no way to create a reflex angle between the two rays.

So either $\angle 102$ is the largest angle in the triangle, making it more than $60 ^\circ$, or it's more than $180 ^\circ$, which would of course still make it more than $60 ^\circ$. We can apply the same logic for $\Delta 023, \Delta034, \ldots, \Delta061$ and find that the central city has 6 angles each of over $60 ^\circ$, which means that the total angle is more than $360 ^\circ$. That's a contradiction since we know it has to be exactly $360 ^\circ$ by construction.

Hence, it's impossible for any city to be connected to 6 other cities this way.

-
-1. The city do not have to be closest for 6 cities. It can be closest for 5 and have one close city for itself. –  klm123 Jul 3 '14 at 5:43
@klm123 Ah, the version I'm familiar with is a theorem about digraphs, but rereading the question, it seems it's about an undirected graph. My proof still works with some modifications, which I'll edit in. –  Logan Maingi Jul 3 '14 at 6:11
I see. So, what exactly you have changed to prove that "It can be closest to 5 other cities"? You start the prove from 6 and I can't find the point where you go from 6 to 5... –  klm123 Jul 3 '14 at 6:30
@klm123 City 0 is closest to exactly one other city, which I pick to be city 1 (because none of the distances are equal according to the problem). So the other 5 cities it's connected to have to be connected by having it as their closest city. We then have 4 triangles where the inequalities I originally showed prove that the side opposite the central angle is longest. For the two triangles containing city 1, we have different (slightly stronger) inequalities which still prove the same thing. –  Logan Maingi Jul 3 '14 at 6:34
@JoeZ. That's a nice way to interpret it. The fact that no three edges ever form a triangle is actually completely obvious; just take the longest edge and show it can't be in the graph. It doesn't rely on anything geometric here, just the definition of the graph itself. (Interestingly and more deeply, the same argument shows a much stronger fact that this graph can't contain any cycles at all; that is to say, it's a forest.)... –  Logan Maingi Jul 3 '14 at 7:21

I'm not sure this is rigorous per se, but I think it's accurate.

Consider some number cities arranged in a circle of radius $r$ around a central city (the "most connected"). The furthest these can be from each other is when they are distributed equally. When there are six cities around the circle, they are all at a distance $r$ from each other. Since each of the cities has exactly one closest city, there cannot be six cities around the circle. If there were more, they would be closer to each other than the central one, so there are strictly less than six cities closest to a single one; since we're working in integers, that means at most five.

-