# Join six cities with roads

Warmup question:

Each of five cities is connected to the others by four roads. Show that it is possible for the roads to intersect only once with exactly two roads crossing over at that single intersection. Junctions at the cities are not considered intersections.

One possible solution is:

The black circles represent the cities. The 8 yellow lines represent the 8 non-intersecting roads. The 2 blue lines represent the 2 roads which intersect and the red dot represents their point of intersection.

Main question:

Each of six cities is connected to the others by five roads. Show that it is possible for the roads to intersect only three times with exactly two roads crossing over at each intersection. Junctions at the cities are not considered intersections.

• @NoName I included the warmup example to help reduce ambiguity in the question. Commented Feb 12 at 4:31
• oeis.org/A000241 Commented Feb 13 at 4:28
• @WillOctagonGibson what attention specifically do you seek? We have a lot of examples here already.
– Sny
Commented Feb 13 at 14:00
• Yea, and there is already an answer by a user with low rep as well, which is usually Will's shtick. And he hasn't replied to any of the answers. Not sure what gotcha he's trying to uncover here, if any. Commented Feb 13 at 14:32
• @WillOctagonGibson because there is a bounty option for "rewarding existing answer", so that's why we asked. No harms done here tho, was just confusing for a moment until you explained it. :) Commented Feb 14 at 3:34

Add a point to the warmup picture like so:

Or like so:

• I upvoted for the paintbrush skills
– Stef
Commented Feb 11 at 15:46
• +1 What a lovely answer! I like how it builds on the five cities diagram. Commented Feb 14 at 3:57

This was not as easy as it first appeared. Here is a solution with a bit of geometric flair:

$${}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}$$

• Very nice graph! Commented Feb 12 at 14:04
• A very elegant (symmetrical) solution! Commented Feb 13 at 8:58
• +1 Welcome to PSE (Puzzling Stack Exchange)! Commented Feb 14 at 5:06

Not as pretty as @Daniel Mathias's but perhaps a bit more obvious:

This is cheating, but at no point does the question say

that each city must be directly connected to each other city by a single road.

Therefore, I propose that we can do better than the solution given to us in the question. In fact, here is a layout with ...

... 0 intersections:

Each city is connected to every other city, and each city has five roads leading away from it. I submit that this matches the problem statement as written, if not the spirit of the question.

Obviously there are many other solutions of this type but this one felt the most whimsical, or something.

• Three of your cities have only three roads each. Commented Feb 13 at 17:34
• Can be fixed by having a circular outer road connecting the 3 cities. Commented Feb 13 at 17:52
• 🤦 can't believe I missed that. thanks for the catch, @RobPratt Commented Feb 13 at 18:07
• Why not just ._._._._._.
– Sny
Commented Feb 14 at 2:24
• +1 A lovely “thinking outside the box” answer. Commented Feb 14 at 4:08

In fact, it is possible with straight lines and looks really cool:

In fact, this is optimal, since each intersection consists of two line segments, each of which is consisted of two points. Hence, if there are only two intersections, we can say that there are eight "contributions". Therefore, each vertex, on average, has more than one "contribution". Hence, at least one vertex has two "contributions". Therefore, by removing that vertex, we have a $$K_5$$ graph with no intersections, which is a contradiction since a planar graph cannot have a $$K_5$$ minor. (Otherwise you'd have a trivial counter-example to the Four Color Theorem as well.)

• Sorry, but I added proof.
– Sny
Commented Feb 13 at 13:56

Don't let yourself get fooled! There is only one solution. It is as folllows:

there are three crossings, ADxBC, CFxDE and EBxFA, shown in red.

The left and the right A and B are the same. The graph needs to be bent to join the two pairs into one.

That can be done in a number of ways:

• +1 This is very interesting in that it shows that all of these posted answers are, in a sense, equivalent. Commented Feb 21 at 21:29