In the capital of the grand country of Appelhaken there is a plane garden containing four magnificent monuments. So magnificent are they that the country has a Law requiring that there must be a clearly marked carpeted path all the way from each monument in the garden to each other monument, and no two such paths may share parts or intersect.

A fifth monument is installed. In order to comply with the Law, the best architect in all of Appelhaken designs a grand and magnificent bridge in the garden, and one path is laid on top of the bridge while another is laid underneath it, for without this bridge the Law could not be upheld.

Shortly afterwards, two more monuments are installed, but there is no more money for additional bridges because the first bridge was too grand. How can the chief gardener of Appelhaken reroute paths to preserve the Law?

enter image description here


The bridge might need to be used for several paths.

  • $\begingroup$ Technically Kuratowski or Wagner could be more appropriate namesakes for this country, but Appelhaken sounded more whimsical. $\endgroup$
    – Magma
    Nov 21 '19 at 18:06
  • $\begingroup$ I think I'm missing a reference. What's the significance of Appelhaken? $\endgroup$ Nov 21 '19 at 18:13
  • $\begingroup$ Appel and Haken proved the four-color theorem, which is almost relevant here. $\endgroup$
    – Magma
    Nov 21 '19 at 19:04
  • $\begingroup$ Baha! A 'magnificent rendering' indeed! ;-) Made me smile...! (see edit history) $\endgroup$
    – Stiv
    Nov 21 '19 at 22:39
  • $\begingroup$ Awww. This got closed as duplicate? After all the trouble I went to making a comprehensible solution to a comprehensible problem, without involving advanced mathematical theory :-( $\endgroup$ Nov 22 '19 at 12:38

Four monuments

Easy map to draw:

4 simple

Or, topologically equivalently (and more usefully for our purposes):

4 better

Five monuments

Starting from the last map above:

5 bridge
(Green is the bridge, with one path crossing over it.)

Seven monuments

Starting from the five-monument map above:

The two new monuments are in red, and new paths in thin lines.

Left red can be connected directly (no bridge use) to three blues: top left, top right, bottom left.
Right red can be connected directly (no bridge use) to three blues: top right, middle, bottom right.

We draw in these six paths right away with thin black lines, but in two cases (left red to top left blue, right red to middle blue), we must choose which side of the existing mini-path (leading up to the bridge) to put the new path. We make the choice in such a way as to block off further access to the top right blue, which is now connected to everything so we don't need it any more.

The remaining paths (left red to middle and bottom right; right red to top left and bottom left; red to red) must cross the bridge. We draw these paths carefully so that they don't cross each other. I've used thin red lines for paths to the right of the existing path on the bridge, thin blue lines for paths to the left of the existing path on the bridge, and the red-to-red path could be on either side so it doesn't matter and I've just used a thin black line.

  • $\begingroup$ @hexomino Yeah, it was a bit trickier than I realised at first to make sure all the bridge paths don't cross each other. I've done it properly now. $\endgroup$ Nov 21 '19 at 17:52
  • $\begingroup$ Note that with one more monument you'd need another bridge, and I think that from that point on each new monument would require at least one more bridge. (Two more for the 12th monument.) $\endgroup$
    – Gareth McCaughan
    Nov 21 '19 at 18:09
  • $\begingroup$ @Gareth Are you sure? A lot depends on exactly where the monuments are placed. If the two red ones here hadn't been in the regions they were in (easily connectible to the bottoms of the existing bridge), we would've needed a new bridge already. $\endgroup$ Nov 21 '19 at 18:12
  • $\begingroup$ I was assuming that we're allowed to reroute the paths when new monuments are placed. [EDITED to add:] As in fact the question explicitly says. $\endgroup$
    – Gareth McCaughan
    Nov 21 '19 at 18:13
  • $\begingroup$ This is basically an embedding of the $K_7$ graph on the surface of a torus. It's kind of a well-known mathematical curiosity. It is known that you cannot embed $K_8$ in the same way, and you'd need to increase the genus, i.e. add another handle/bridge. $\endgroup$ Nov 21 '19 at 18:44

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