Mathematical Recreations

MathRec Home
Solutions to this Problem
Last Month's Problem
Introductory Problem
Older Problems
and Links
Educational Resources
Steve's Personal Page

Fully Connected Graphs On The Torus (November 2001)

There was a discussion in the old Mathematical Recreations feature of Scientific American about graphs and line crossings. This problem was directly inspired by that article.

A graph in this context is a set of points (nodes) which are connected by lines. A fully connected graph is a set of points where every point is joined to every other point by one line. A triangle is a fully connected graph with three nodes. A square with the diagonals connected is a fully connected graph with four nodes. The fully connected graph with n nodes is denoted by Kn.

The Scientific American article concerned the minimum number of line crossings which are needed to draw different graphs on a two-dimensional plane. For example, K4 can be drawn as a square with the diagonals connected by straight lines. Since the diagonals cross, there is one line crossing. But the same graph can be drawn with one diagonal connected inside the square and the opposite diagonal connected by a curved line outside the square. In that case, the graph is drawn without any line crossings.

The article described line crossings as bridges and said the problem was equivalent to asking for the minimum number of bridges (and then went on to talk about how this sort of graph theory is useful for designing circuit boards.) I thought that was a silly analogy, since you can run more than one path across the same bridge without having the lines cross. That led me into a new area of investigation...

So, what's the answer? What is the largest fully-connected graph which can be constructed using a single bridge? We can start by realizing that a plane with a bridge is topologically equivalent to a torus. (Which is topologically equivalent to any surface with one handle, such as a tea cup.)

This problem isn't really too difficult. Although proving it requires some knowledge of topology. Some additional areas to investigate involve surfaces with two handles (bridges) or n handles. I had fun with those questions, but didn't dig too deeply the first time through. I got pulled into another direction by this problem. You might want to consider what the graph in question looks like on a torus when you shorten up the lines as much as possible. But enough of that—I don't want to spoil the answer.


Send all responses to my email address is mathrec at this domain.

Thanks,
Steve