8
$\begingroup$

A complete graph of $n$ nodes is a graph where every node is connected to every other node. It is known that one cannot draw a complete graph of 5 nodes on a piece of paper (plane) without any crossing edges. However it is possible to draw this graph on a donut (torus) without any crossing edges. How can you do it? Bonus question 1: how can you draw a complete graph of 6 nodes on a torus without any crossing edges? Bonus question 2: what about a complete graph of 7 nodes?

$\endgroup$
3
  • $\begingroup$ Quick search reveals that the answer is rot13(lrf sbe nyy guerr dhrfgvbaf). The intention here is to provide a concrete example of how to draw it, right? $\endgroup$
    – Bubbler
    Oct 19 '20 at 1:17
  • $\begingroup$ Yes a concrete example please. $\endgroup$ Oct 19 '20 at 1:24
  • 1
    $\begingroup$ That's an interesting question because a torus can be represented as a graph, different from the graph representation of a 2d plane, so the question becomes about identifying graph subsets or projections. $\endgroup$
    – Frank
    Oct 19 '20 at 9:28
12
$\begingroup$

Here is a picture of the 5 graph:

enter image description here

A flat version (perodic boundaries) is easier to digest and reveals the fundamental symmetries:

enter image description here

and of the 6 graph:

enter image description here
We could have used the same pattern as in the 5 and 7 cases but chose a (slightly) different arrangement instead.

and the 7 graph:

enter image description here

Flat version (perodic boundaries). We can see that this construction maxes out at 7. Please note how simple and clear this representation is. It gives a good intuition of how the torus offers us an additional back alley and why we can neatly make six connections per node.

enter image description here

$\endgroup$
1
  • 1
    $\begingroup$ All of the answers were great, but I decided to go with this one because it has the nicest 2D patterns. Well done! $\endgroup$ Oct 19 '20 at 10:19
10
$\begingroup$

Start with this 'snowflake' pattern:


enter image description here

We can see that each of the 7 digits in the center has all 7 other digits next to it. If we can connect the gray digits to the appropriate place by wrapping around the torus, we're done.

So, we can do it like this:


enter image description here

This can be placed on the side of the torus: the lines that run off the left edge go all the way around and end up on the right side. The lines that run off the top edge go through the hole in the middle and end up on the bottom. And so all of the connections are established.


There's another way to look at it that's based off:

the 7-coloring of the plane. If we take this pattern:
enter image description here
here, and repeat it over and over, every color touches every other color. If we draw lines from the center of each region to each one that touches it, we're done! Each of the 7 colors here touches all of the other 7, and so the graph of their centers will be the complete graph on 7 vertices.

The only minor issue is that we have infinitely many vertices labelled with each number from 1 to 7, rather than one of each.
All that's left is to make all of those colors the same region. To do this, we can use the topology of the torus! Take the graph, and cut out a section that we want to repeat forever:

enter image description here

Now, look at this square we can get by distorting it:
enter image description here

enter image description here
If we stretch this square out into a really long rectangle...
enter image description here
...we can wrap this around the outside edge of the donut, and then stretch the bottom and top sides to connect through the hole. This means that there are only 7 regions, and they all touch each other -- exactly what we wanted!

$\endgroup$
3
  • 1
    $\begingroup$ Two people answered while I was busy making the diagrams for the second half. Could've just posted the first part as-is -- hopefully the diagrams were worth the wait. (If anyone knows of a nice way to actually display the last part on a donut, please show it off! I'm not familiar with any 3d modelling software, so I wouldn't know how to apply this as a texture.) $\endgroup$
    – Deusovi
    Oct 19 '20 at 2:24
  • 1
    $\begingroup$ The second approach is definitely interesting, as it does the best job at showing the regularity of the embedding. $\endgroup$
    – Bubbler
    Oct 19 '20 at 2:34
  • $\begingroup$ Very nice 7-coloring. Thank you. $\endgroup$ Oct 19 '20 at 10:21
9
$\begingroup$

Since the surface of a donut (or toroid) is topologically equivalent to a rectangular space with both pairs of edges wrapping, we can represent a toroidal embedding of a graph as such (which is also easier to see than a drawing on an actual toroid).

$K_5$ is easy:

$K_6$ is a little bit harder:

$K_7$ requires serious thought, because

we have 7 nodes and 21 edges to draw, which requires us to draw a triangulation of the toroidal surface.

I ended up drawing the following:

This shows four copies of the hexagonal subgraph to make the wrapping edges easier to follow. If you imagine the entire figure moving horizontally and vertically and overlap the hexagons, you can see that no edges cross any other edge.

$\endgroup$
3
  • $\begingroup$ I think you've got it! This is a nice way to draw it. If you want to see an actual drawing on a torus then see Figure 1 from this paper: jgaa.info/accepted/2011/DuncanGoodrichKobourov2011.15.1.pdf $\endgroup$ Oct 19 '20 at 2:14
  • $\begingroup$ @DmitryKamenetsky Ooh, that's horrible :P $\endgroup$
    – Bubbler
    Oct 19 '20 at 2:19
  • $\begingroup$ You're missing lines from your top left to top right nodes in your first image. Otherwise great answer! :) $\endgroup$
    – Chris
    Oct 19 '20 at 10:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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