Mathematics 5
Winter Term 2000
The World According to Mathematics

Dwight Lahr and Josh Laison

Friday Discussion: Week #5

1.

Review of homework from this week.

2.

Problems *7 and *8 from Part 4 of the Graph Theory handouts.

3.

A planar graph is a graph that can be drawn in the plane with no edge-crossings.
There are other surfaces that a graph can be drawn on, such as a torus (the surface of
a doughnut or a bagel). For any graph G, we can ask whether Gcan be drawn on a
torus with no crossings. The best way to think about it is to imagine cutting the torus
twice and laying it out flat, as in the picture below. Then any edge that goes off the
side of the square comes back on the other side, and any edge that goes off the top
comes back on the bottom.

[Picture]

In general it is easier to draw a graph on a torus than on a plane. Here is a picture of
the complete graph on 5 vertices drawn on a torus with no crossings.

[Picture]

Can the complete graph on 6 vertices be drawn on the torus with no crossings? What
about the complete graph on 7 vertices?