Show how to draw the complete graphs K6 and K7 on a torus, with no two edges crossing.
geometry/topology/complete.graphs.on.torus New
New entry, edited from material collected for the archive and not yet in a released version.
Problem
Show how to draw the complete graphs K6 and K7 on a torus, with no two edges crossing. Finally, my puzzle: Show how to draw K6 and K7 on a torus. (Both can be done.) K6 is fairly straightforward. K7 is (at least for me it was) *hard*. -- magliery@s.cs.uiuc.edu
Show solution
Below is a sketch of K6 on a torus.
I'm not following Magliery's [Editor: "Maglieri's" in the original]
format exactly. I represent the torus as a rectangle, with the left and
right vertical sides identified (without a twist), and with the top and
bottom edges identified (without a twist). This format is fairly
standard, BTW, and with different identifications can represent a
cylinder, moebious strip, klein bottle, or sphere (identify entire
perimeter at one point). Letters at the perimeter show intended
matching of lines, and you can verify that there is no cheating by
hidden crossings.
The picture got a little messed up, but I think you can tell where all
the lines are supposed to go.
c a b
------|-----|---------------|--------------
| | | | |
| \ | | |
| \ | | |
| \ | | |
| \--| | /-----------|d
| 1 ------------- 4 |
d|--\ | \ | \-----------|e
| \ | \--------- \ | |
| \-----\| \| |
e|--\ 2 ------------- 5 \ |
| \ |\ | \----------|f
| \----\ | \---------\ | |
f|----------\| \ | /---|g
| 3 ------------- 6--------/ |
g|---------/ | |\ \----------|c'
| | | |
c'|----+ | | |
| | | | |
------------|---------------|--------------
c a b
1-2 direct 1-3 around top (a) 1-4 direct 1-5 direct
1-6 around top (c),around left (c')
2-3 direct 2-4 around left (d) 2-5 direct 2-6 direct
3-4 around left (e) 3-5 around left (f) 3-6 around left (g)
4-5 direct 4-6 around top (b)
5-6 direct
-- Mitch Marks <mitchell@cs.UChicago.EDU>
First, an "aesthetic" correction to my posting giving K6: the line
3-e-4 should wrap arround vertically, starting out SE from 3, hitting
bottom edge at e halfway inbetween a and b, and going from
corresponding point e on the top edge SE to 4. This makes it
"parallel" to the direct 1-5 and 2-6 connections. This just makes it
cleaner-looking, so far as I know the posted solution was not
incorrect.
K7:
I'm not enough of a picture hacker to draw the lines in. The rectangle
and lettered perimeter points should be understood as described in my
posting giving K6: the top and bottom edges are identified, the left
and right edges are identified, and the letters mark specific points
where the lines (if they were drawn in) are understood to wrap around.
After the diagram, I describe the path for each pair of nodes; and the
letters help verify that there is no hidden crossing.
h g a e f i'
|--------------------------------------------------------------|
| |
i| |i
| |
f'| 3 |f'
| |
b| 1 6 |b
| |
| 4 |c
c| |
| 2 |
| 7 |
| |
d| 5 |d
| |
| |h'
h'| |
|--------------------------------------------------------------|
h g a e f i'
1-2: direct 1-3: direct 1-4: direct
1-5: 1-f', around left, f' to f at NE corner, around top, f-5
1-6: around left (b)
1-7: 1-i, around left, i to i' at NE corner closer to corner than f'-f,
around top to i' at bottom, i' to 7.
2-3: around bottom (g) 2-4: direct 2-5: direct
2-6: around left (c) 2-7: around left (d)
3-4: direct 3-5: around top (a) 3-6: direct
3-7: 3-h, around top to h, h to h' at SW corner, h' around left, h' to 7
4-5: direct 4-6: direct 4-7: direct
5-6: around bottom (e) 5-7: direct
6-7: direct
(This all makes sense on the paper diagram I have sitting on my desk,
which has the lines drawn in; I don't know if it can be visualized
on-screen without the lines, but trying to put them in resulted in
unmanageable clutter. Of course, if anyone wants to go to that much
trouble, you can get out your own piece of paper and draw the lines.
:-)
-- Mitch Marks <mitchell@cs.UChicago.EDU>
One good way to solve this problem and better yet, to make it
transparent that you have a correct solution (the hard part) follows:
Draw a square lattice in the plane (i.e. put a dot on every point with
integer coordinates). Draw edges connecting each vertex to its
vertical and horizontal neighbors. Now, draw each of the lines
y = -x + b for integer b (thus connecting each vertex to its southeast
and northwest neighbors).
Now, it's easy to see that every vertex in this grid has edges
connecting it to 6 other vertices, and that none of the edges cross.
So what does this have to do with drawing K7 on a torus? Easy.
The surface of a torus can be represented (as has been pointed out) by
slicing the torus once through a radius and then once around its outer
equator, flattening it out into a rectangle. Fine. Look at the grid
we drew above. Slice it between the points (0,0) and (2,1), and also
between (0,0) and (1,4), between (1,4) and (3,5), and between (2,1)
and (3,5) [Editor: "3.5)" in the original]. Now, "tape" the opposite
edges of this parallelogram together (you wont get a very _pleasing_
torus without a lot of stretching so you may struggle if you try this
with paper and scissors, but topologically it's a torus) thus joining
the four points at the corner into a single vertex. Viola!
If you want a torus you can actually sort of construct by hand without
struggle, a simple computer program (or a lot of number cruncing) could
be used to map that parallelogram to a rectangle, by multiplying each
point by the matrix
- -
1 | 8 -2 |
/ 7 | -4 8 |
- -
(interestingly enough, we did this in my combinatorics class the other
day, so credit goes to Prof. Mark Haiman at MIT, not me).
Discaimer: I haven't tried the bit with the linear transformation
yet, so I may have misplaced a number. I'm a math major: we don't do
arithmetic. 8-)
[ Editor: the poster is not named in the collected copy. ]
Here's another picture for K7 on a torus. We did this a couple of
weeks ago in my graph theory class. I think it's a "pretty" picture.
Note: Point "1" is identified at all 4 "corners" of the picture. This
really is legal, though. The other six points, not labeled, are just
the six places where the lines interect. I'm sorry the lines don't
appear to be perfectly straight; if you draw it on paper, though, they
can all be perfectly straight. Just bisect/trisect the edges of a
square. The six interior points are (each) the intersection of three
lines.
1----------------a-----e----------b----------------1
|\_____ / ...: / .../|
| \_____ /..: / ....: / |
| ..\/____ / ....: / |
| ...: / \_____ / ....: / |
| ...: / \___/_.: / |
d|.: / ....:/ \_____ / ..|d
| / ....: / \_____ /...: |
c|_____ / ....: / ....X_______|c
| \_/___: / ....: / |
| ....:/ \_____ / ....: / |
f|: / \____/....: / ....|f
| / ....:/ \_____ / ....: |
| / ....: / \_____ /..: |
| / ....: / ..\/____ |
| /...: / ....: / \_____ |
|/: / ....: / \__|
1----------------a-----e----------b----------------1
[ Editor: the poster is not named in the collected copy. ]
In article <217600107@s.cs.uiuc.edu> magliery@s.cs.uiuc.edu writes:
>Finally, my puzzle: Show how to draw K6 and K7 on a torus. (Both can
>be done.) K6 is fairly straightforward. K7 is (at least for me it
>was) *hard*.
An easy way to see it can be done is to start with a triangular
lattice in the plane, and label the vertices with a number from 1 to 7
as follows:
1--2--3--4--5--6--7--1--2--3--4
\/ \/ \/ \/ \/ \/ \/ \/ \/ \/
4--5--6--7--1--2--3--4--5--6
/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \
6--7--1--2--3--4--5--6--7--1--2
\/ \/ \/ \/ \/ \/ \/ \/ \/ \/
2--3--4--5--6--7--1--2--3--4
so there's an index-7 sublattice, again triangular, consiting of
precisely those translations that preserve the labelling. (You can
think of the lattice as the Eisenstein integers and the sublattice as
one of the two prime ideals dividing (7).) The quotient of the plane
by this sublattice is a torus that comes with a K7 (since the six
neighbors of any vertex in the triangular lattice are labelled with the
six numbers other than its own label). Of course, having obtained a K7
one easily gets a K6 by deleting one vertex.
Exercise: use Euler's formula to show that one cannot draw K8 on a
torus. Generalize to other surfaces.
-- Noam D. Elkies <elkies@zariski.harvard.edu>