14
$\begingroup$

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:

enter image description here

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.


The six cities question is from a Leningrad Mathematical Olympiad.

$\endgroup$
12
  • 1
    $\begingroup$ @NoName I included the warmup example to help reduce ambiguity in the question. $\endgroup$ Feb 12 at 4:31
  • 1
    $\begingroup$ oeis.org/A000241 $\endgroup$
    – RobPratt
    Feb 13 at 4:28
  • 4
    $\begingroup$ @WillOctagonGibson what attention specifically do you seek? We have a lot of examples here already. $\endgroup$ Feb 13 at 14:00
  • 2
    $\begingroup$ 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. $\endgroup$
    – justhalf
    Feb 13 at 14:32
  • 1
    $\begingroup$ @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. :) $\endgroup$
    – justhalf
    Feb 14 at 3:34

7 Answers 7

31
+200
$\begingroup$

Add a point to the warmup picture like so:

Or like so:

$\endgroup$
3
  • 5
    $\begingroup$ How did I miss this? $\endgroup$ Feb 11 at 2:51
  • 12
    $\begingroup$ I upvoted for the paintbrush skills $\endgroup$
    – Stef
    Feb 11 at 15:46
  • $\begingroup$ +1 What a lovely answer! I like how it builds on the five cities diagram. $\endgroup$ Feb 14 at 3:57
21
$\begingroup$

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

enter image description here

$\endgroup$
16
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ Very nice graph! $\endgroup$ Feb 12 at 14:04
  • 2
    $\begingroup$ A very elegant (symmetrical) solution! $\endgroup$ Feb 13 at 8:58
  • $\begingroup$ +1 Welcome to PSE (Puzzling Stack Exchange)! $\endgroup$ Feb 14 at 5:06
7
$\begingroup$

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

enter image description here

$\endgroup$
4
$\begingroup$

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:

a connected graph with six nodes, each connected to five edges

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.

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

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

enter image description here

Edit: whoops, pumpkin star already got this... upvote his answer plz

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.)

$\endgroup$
1
  • 1
    $\begingroup$ Sorry, but I added proof. $\endgroup$ Feb 13 at 13:56
1
$\begingroup$

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

enter image description here

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:

enter image description here enter image description here enter image description here enter image description here enter image description here

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.