Complete Toroidal Graphs I've seen it referenced that $K_N$ is a toroidal graph for $N \leq 7$.  Can anyone supply a proof (source link or outline) that $K_8$ is not a toroidal graph?
 A: This is a consequence of the Heawood Conjecture, which gives a formula for the maximal number of colors needed for a graph coloring of a surface with a given genus---called the chromatic number of such a surface. Despite its name, was settled positively in 1968 by Ringel and Youngs. (The genus $0$ case is precisely the topic of the celebrated Four Color Theorem.) 
In particular, it gives that for a torus, which has genus $1$, the maximal number of colors needed is $7$ (in fact, this case was settled by Gustin and Youngs a few years before the general theorem). Since $K_8$ requires eight colors, it cannot be embedded in the torus, i.e., it is not toroidal. (The above theorem implies that $K_8$ can be embedded in a surface of genus $2$ and that $K_9$ cannot.)
A: We first show that any embedding of $K_8$ into the torus must be a $2$-cell embedding (that is, the complement of $K_8$ in the torus consists of some number of regions/faces homeomorphic to open disks).  We can 'build' such an embedding in pieces, but first embedding an $8$ vertex tree on the torus (clearly possible), and then adding edges between two vertices in such a way that each new edges only intersects other edges at its endpoints.  Then, the complement of the original tree graph is homeomorphic to a torus with a point removed, and no matter how we choose to add an edge,  the 'faces' of the embedding of $K_8$ into the torus will consist of tori with a single point removed, cylinders, or disks *<\sup>.  If one of the faces were a torus with a point removed, then the complement of this face would be homeomorphic to a closed disk, and we would have an embedding of $K_8$ into the plane.  On the other hand, if one of the faces were a cylinder, then it's complement would be a closed cylinder, and we could sew an open disk onto one of the boundaries to obtain a closed disk, again giving us an embedding into the plane.  Since $K_N$ is nonplanar for $N\ge 5$, any embedding of $K_8$ into the torus must be a $2$-cell embedding$^\dagger$.
Suppose $K_8$ had a $2$-cell embedding in the torus.  Then, this embedding has $v=8$ vertices and $e=28$ edges.  Since the Euler characteristic, $\chi$ of the torus is $0$, we have by Euler's formula that the number of faces is:
$$f=\chi + e - v = 20$$
Suppose each face is bounded by, on average, $k$ edges ($k$ may not be an integer).  Then, $kf$ exactly double counts the number of edges of the graph (since each edge separates $2$ faces), so
$$kf = 2e$$
But, since $K_8$ is a simple graph, we must have $k \ge 3$, so we must have
$$3f \le 2e$$
$$60 \le 56$$
which is clearly not the case$^\ddagger$.

*: To see this, consider the torus as an identification polygon (image credit Wikipedia):

the original tree graph can be chosen to lie in the interior of this region.  As we add new edges, we can either remove small, disk faces from the larger face, or completely cut the identification polygon into two pieces, each containing one of the colored edges $A$ or $B$.  When we do this, we can glue these colored edges together to obtain a single face, which will be either a cylinder (if the original face was a torus with a point removed) or a disk (if the original face was a cylinder).
$\dagger$: Nowhere does this argument depend the fact that $K_8$ has $8$ vertices.  We can make the same argument for $K_N$ for any $N\ge 5$.  
$\ddagger$: Again, this argument can be adapted for $K_N$, $N\ge 8$.  Note that the number of faces, $F_N$, is $F_N = e_N-v_N = \frac{N(N-1)}{2} - N = \frac{N(N-3)}{2}$, and
$$3f_N = \frac{3}{2}N(N-3) > N(N-1) = 2e_N$$
for $N\ge 8$.
