Fully Connected Graphs On The Torus (November 2001)
The largest fully connected graph which can be drawn on the torus without line crossings has seven nodes. Here is a representation of the solution. In order to make it easier to see how the links connect from one edge of the square to the other, I've colored the region around each node a different color.
There are several interesting things to talk about here. We can start with the different surfaces which are topologically equivalent to the torus. I've drawn the torus as a square with periodic boundary conditions, for example. You get a torus by rolling it up along one axis, then the other. A plane with a bridge is also topologically equivalent to a torus (except for the point at infinity).
Next, you should note the windings of the torus. Notice that the links between nodes run in one of three different directions. If you trace any link through successive nodes, you'll find that there are three different loops, each of which passes through all seven nodes (in different order). The loop running from lower left to upper right wraps around twice in the vertical direction while wrapping once in the horizontal direction. The lines which are most nearly horizontal wrap around three times in the horizontal direction while wrapping once in the vertical direction. Finally, the other set of lines wraps three times in the vertical direction while wrapping twice in the horizontal direction.
This was my introduction to windings of the torus. I found it very interesting that the torus could be wound with three turns on one axis and two on the other without having the lines overlap. If you haven't looked at it before, you might want to answer the following question: "What winding numbers (n, m) on the torus are possible for a single loop (without line crossings)?" You can find the answer here.
Finally, I found it pretty interesting that you could only get K4 on a sphere (without line crossings), but you could get K7 on a torus. OK, admittedly, you only need one line crossing to get K5, but I still thought that was a pretty big jump.
As it turns out, a lower limit for the number of handles (bridges) required to draw Kn without line crossings can be found if you know some topology. If you consider any compact two-dimensional surface and cover it with triangles (such that there are no handles inside any triangle), then the following quantity is always the same for any such triangulation of that surface:
The quantities v, e and f are the numbers of vertices, edges and faces respectively. This quantity χ is called the Euler Characteristic.
Using the Euler Characteristic, you can prove that the graph of K8 cannot be drawn on a torus without line crossings, You can also prove that a graph of K9 cannot be drawn on a plane with only two bridges. It's interesting to explore how the Euler Characteristic works. Then we can use it to answer our general question.
For this discussion, we are only concerned with surfaces that can exist in three dimensions and have a well-defined distinction between top and bottom or between inside and outside. All such surfaces are homeomorphic to the plane with some number of bridges (handles or holes. A plane with a single bridge can be stretched without tearing into the shape of a torus (with a point where the plane goes to infinity and a point which was the underside of the bridge.)
If you carve any of these surfaces up with vertices and edges such that every face is homeomorphic to a simple disk or polygon, then you will always get the same value for χ. You can demonstrate this to yourself by observing that χ doesn't change when you add vertices and line segments to an existing graph with this property, and also observing that you can remove vertices and edges and χ doesn't change (as long as you never join a face to itself). Proving it might be a bit tricky, but this is a recreational site, so we will be content with showing that it is true.
Once you've convinced yourself that you can add or remove vertices and edges without changing χ, it's a simple trick to show that χ is the same for all graphs which cover the surface (leaving only faces homeomorphic to a disk). That is, you can change any such graph into any other by adding and removing vertices and line segments, while never connecting a face to itself. Simply start with the first graph; overlay the second graph on it, adding all of the vertices and edges of the second graph. Wherever the two graphs cross, add a new vertex and split both edges. Then remove the old graph; remove any extra vertices that you created and rejoin the edges. All of the graphs in the transition from the old graph to the new graph were composed of one of the two graphs with additional vertices and edges. Therefore, none of the transitional graphs had any face which was not homeomorphic to a disk, and χ is the same for both graphs.
So any graph that carves up a surface has the same Euler Characteristic. That is, χ is a fundamental property of the surface. It is trivial to show that χ is two for a plane or a sphere. If you add a handle to an existing surface, how does that change the Euler Characteristic? Well, it's fun to play with it, and I encourage you to do so. Here's one approach.
The Euler Characteristic of a Torus is zero. (For example, the graph above has seven vertices. Each vertex has six edges, so there are 21 edges. Each face is a triangle, so there are fourteen faces.) We can join the torus to a plane by removing one of the faces and connecting the torus to a plane with the same sized face removed. We have just added one handle, one hole or one bridge, depending on your favorite term. We still have a graph with the right properties (since the outside of a polygon on a plane or sphere is homeomorphic to a disk). In fact, if we wrap the plane around, as though it's the surface of a sphere with an infinite radius, then shrink that infinte bulge down to a triangle, we see that what we got when we joined the torus to the plane was just a torus. (If you are still not comfortable thinking about the plane and the sphere as homeomorphs, think about it for a bit.)
What we've done is lower the Euler Characteristic of the sphere or plane by two when we joined it with the torus. Let's join the torus to an arbitrary surface with Euler Characteristic χ. Let's create graphs which cover each surface. Now take a polygon with N vertices from each surface, remove the two faces and join the two surfaces at the polygon. You also lose N vertices and N edges. Now you have a graph which covers the combined surface and has Euler Characteristic χ – 2.
If you need to think of a handle as going from one part of the surface to another instead of being a torus joined at a single location, that's OK. Take two separated polygons with N vertices on the same surface. Remove the two faces. Connect the two polygons with a tube, then connect the corresponding vertices of the two polygons across the tube. You've removed two faces, but added N more. You've also added N edges, but you haven't changed the number of vertices. The Euler Characteristic is decreased by two.
Now suppose you have a surface which contains Kn without any line crossings. Suppose, for a moment that the graph covers the surface so that every face is homeomorphic to a disk. (If it doesn't, then you can just remove one or more handles.) Kn has n vertices and n(n –1)/2 edges. The average number of edges on each face is at least three, since Kn has no nodes connected to themselves and no two nodes connected to each other twice. Therefore, there are at most n(n – 1)/3 faces. We find
Since the number of handles is equal to 1 – χ/2, we find that the number of handles g is limited by
For K8, we find that two bridges might do the trick. We know that K8 has eight vertices and 28 edges. On a two-handled surface, it must have eighteen faces, since χ = –2. In fact, I've found such a graph (with two quadrilateral faces). There is no way to get K9 onto a two-handled surface.
Apparently it has been proven not only that g must satisfy the inequality above, but that if g does satisfy this inequality, then the graph can be drawn without edge crossings. I haven't had a chance to look up the proof, but it is reported by Edward Early that Michael Henle provides a proof in "A Combinatorial Introduction to Topology" (Dover, 1994). This then completes the quest.
Many thanks to Kevin Perry at Princeton University for setting me on the right track.Thanks,
Send all responses to .