Toroidal Embeddings of K5 and K3,3

From Vertex Rotations to Toroidal Embeddings

A graph can be drawn on a surface without crossings even when it cannot be drawn in the plane without crossings. The complete graphs \(K_5\) and \(K_{3,3}\) are basic examples: neither is planar, but each can be embedded on the torus. To establish this precisely, we will specify cyclic orders of the edges around each vertex, trace the resulting face boundaries, and check the Euler characteristic.

All graphs in this tutorial are finite and simple. An embedding places vertices at distinct points of a surface and represents each edge by an arc so that edge interiors do not intersect one another or vertices. An embedding is cellular if each region complementary to the drawing is an open disk; these regions are its faces. The orientable genus of a graph is the least genus of an orientable surface on which it has an embedding. The torus has genus one and Euler characteristic \(0\).

Definition: A rotation at a vertex is a cyclic order of the edges incident with that vertex. For an orientable embedding, choose a consistent direction around all vertices. To trace a face boundary, follow an edge to a vertex and then leave along the edge immediately succeeding the incoming edge in that vertex’s cyclic order. A collection of rotations is called a rotation system.

A rotation system specifies an orientable cellular embedding as follows. Take a small disk for each vertex and attach a narrow band for each edge, with the bands arranged around each disk in the specified cyclic order. The resulting surface with boundary is orientable; tracing its boundary components follows the face rule above. Cap each boundary component with a disk. The graph is then embedded cellularly, with one face for each boundary component. In particular, if the tracing gives \(F\) face boundary walks, then the resulting closed surface has Euler characteristic \(n-m+F\).

A Rotation System for \(K_5\)

Worked Example: Five Quadrilateral Faces of \(K_5\)

Use residues modulo \(5\) as vertices. Explicitly, let \(V=\{0,1,2,3,4\}\) and \(E=\{01,02,03,04,12,13,14,23,24,34\}\), so this graph is \(K_5\). At each vertex \(x\), prescribe the cyclic neighbor order \(x+1,x+2,x+4,x+3\), with all entries calculated modulo \(5\). For instance, at vertex \(3\) the order is \(4,0,2,1\).

For \(x=0,1,2,3,4\), the face rule gives the boundary walk \(F_x=(x,x+1,x+4,x+3,x)\), with arithmetic modulo \(5\). Written out, the five boundaries are:

\(F_0: 0,1,4,3,0\).
\(F_1: 1,2,0,4,1\).
\(F_2: 2,3,1,0,2\).
\(F_3: 3,4,2,1,3\).
\(F_4: 4,0,3,2,4\).

For example, after the walk reaches vertex \(x+1\) from \(x\), the incoming neighbor is \(x\), which is \(x+4\) in the cyclic order at \(x+1\). Its successor is \(x+3\), so the walk continues to \(x+4\). Applying the same rule at the next two vertices gives \(x+3\), then \(x\), as listed.

Here is a check that the boundaries use every edge exactly twice, once in each direction. As \(x\) ranges over the five residues, the first step \(x\to x+1\) uses each directed edge of difference \(+1\) once. The third step \(x+4\to x+3\) uses each directed edge of difference \(-1\) once. The second step \(x+1\to x+4\) has difference \(+3\), or \(-2\), and uses each directed edge of that difference once; the fourth step \(x+3\to x\) has difference \(+2\) and uses each of those directed edges once. These are the four possible nonzero differences modulo \(5\), so every undirected edge appears in both directions among the face boundaries.

Thus the rotation system gives a cellular embedding with \(n=5\), \(m=10\), and \(F=5\). Substitution into Euler’s formula gives \(n-m+F=5-10+5=0\), the Euler characteristic of the torus. The embedding is therefore on an orientable surface of genus one.

Check: each of the five listed boundaries has length \(4\), so the total face-boundary length is \(5\cdot4=20\). There are \(10\) edges, each counted twice, giving \(2\cdot10=20\) as required.

A Rotation System for \(K_{3,3}\)

Worked Example: Three Hexagonal Faces of \(K_{3,3}\)

Let \(V=\{a_0,a_1,a_2,b_0,b_1,b_2\}\) and \(E=\{a_i b_j: i,j\in\{0,1,2\}\}\). This is the simple complete bipartite graph \(K_{3,3}\), with \(n=6\) and \(m=3\cdot3=9\). Indices in what follows are calculated modulo \(3\). At every \(a_i\), put the neighbors in cyclic order \(b_0,b_1,b_2\); at every \(b_j\), put them in cyclic order \(a_0,a_1,a_2\).

For \(d=0,1,2\), tracing the face rule gives \(F_d=(a_d,b_0,a_{d+1},b_1,a_{d+2},b_2,a_d)\). In full, the three boundaries are:

\(F_0: a_0,b_0,a_1,b_1,a_2,b_2,a_0\).
\(F_1: a_1,b_0,a_2,b_1,a_0,b_2,a_1\).
\(F_2: a_2,b_0,a_0,b_1,a_1,b_2,a_2\).

For the tracing rule, after arriving at \(b_j\) from \(a_i\), the next vertex is \(a_{i+1}\), since the successor of \(a_i\) at \(b_j\) is \(a_{i+1}\). After arriving at \(a_{i+1}\) from \(b_j\), the next vertex is \(b_{j+1}\). Repeating these two steps produces exactly the displayed six-edge walks.

To verify edge use, fix any \(a_i b_j\). In the displayed face \(F_d\), the step from \(a\) to \(b\) at index \(j\) is \(a_{d+j}\to b_j\). Exactly one residue \(d\) satisfies \(i=d+j\) modulo \(3\), so the edge occurs once in the direction \(a_i\to b_j\). The reverse step from \(b_j\) to an \(a\)-vertex in \(F_d\) is \(b_j\to a_{d+j+1}\). Exactly one \(d\) satisfies \(i=d+j+1\) modulo \(3\), so the edge also occurs once in the direction \(b_j\to a_i\). Thus all nine edges occur twice, oppositely directed, in the face boundaries.

The rotation system therefore gives a cellular orientable embedding with \(F=3\). Its Euler characteristic is \(n-m+F=6-9+3=0\), so the surface is the torus.

Check: the total face-boundary length is \(3\cdot6=18\). Counting each of the \(9\) edges twice also gives \(2\cdot9=18\).

Euler Characteristic and Genus

For a connected cellular embedding on a closed orientable surface of genus \(g\), Euler’s formula is \(n-m+F=2-2g\). In both constructions, the face walks have been checked directly, and the graph is connected. For \(K_5\), \(n-m+F=5-10+5=0\); for \(K_{3,3}\), \(n-m+F=6-9+3=0\). Consequently, each constructed surface satisfies \(2-2g=0\), so \(2g=2\) and \(g=1\).

Theorem: The orientable genus of each of \(K_5\) and \(K_{3,3}\) is exactly one.

Proof. The rotation systems above give embeddings of both graphs on the torus, so each orientable genus is at most \(1\). For the lower bounds, use the surface edge bounds established in the earlier material on surface edge bounds: a simple graph with \(n\ge3\) embedded on an orientable surface of genus \(g\) satisfies \(m\le3n-6+6g\); if the graph is bipartite, it also satisfies \(m\le2n-4+4g\). These bounds apply to minimum-genus embeddings, which may be taken cellular. For \(K_5\), the first bound gives \(10\le3\cdot5-6+6g=9+6g\), hence \(g\ge1/6\). Since orientable genus is a nonnegative integer, \(g\ge1\). For \(K_{3,3}\), which is bipartite, the second bound gives \(9\le2\cdot6-4+4g=8+4g\), hence \(g\ge1/4\), and again integer-valued genus gives \(g\ge1\). Combining these lower bounds with the torus embeddings proves that both genera equal \(1\). \(\square\)

The lower bounds are essential: Euler’s formula verifies which surface the constructions produce, but does not by itself rule out an embedding on a surface of smaller genus. The edge bounds rule out genus \(0\), while the explicit rotations establish that genus \(1\) is attainable.

Worked Example: Checking the Genus Lower Bounds

For \(K_5\), substitute \(n=5\) and \(m=10\) into the simple-graph surface bound. At genus \(g=0\), its right-hand side is \(3\cdot5-6+6\cdot0=9\), which is less than \(10\); so genus zero is impossible. At genus \(g=1\), the right-hand side is \(3\cdot5-6+6\cdot1=15\), so the bound permits the torus embedding. The exact genus is one because the rotation construction already supplies that embedding.

For \(K_{3,3}\), use the bipartite bound. At \(g=0\), its right-hand side is \(2\cdot6-4+4\cdot0=8\), less than \(m=9\), so genus zero is impossible. At \(g=1\), it is \(2\cdot6-4+4\cdot1=12\), and the construction supplies an embedding on that genus-one surface. Again, the lower bound and the construction together give exact genus one.

Check: the genus-zero inequalities fail by one edge in each case: \(10-9=1\) for \(K_5\), and \(9-8=1\) for \(K_{3,3}\).

Common Pitfall: Using the Wrong Edge Bound

The general simple-graph edge bound is valid for \(K_{3,3}\), but it is too weak to prove that \(K_{3,3}\) is nonplanar. At \(g=0\), it gives \(m\le3\cdot6-6=12\), and \(9\le12\) is true; this calculation does not rule out a planar embedding. The correction is to use the sharper bound for bipartite graphs: \(m\le2\cdot6-4=8\) at \(g=0\), whereas \(K_{3,3}\) has \(9\) edges. Thus \(9\le8\) is false, proving genus at least one.

A second check is to avoid inferring a surface just from the number of edges or the number of vertices. The rotation system matters: its face boundaries must be traced, and the resulting \(n-m+F\) must match the Euler characteristic of the claimed surface. In these examples, verifying that every edge appears exactly twice with opposite directions also checks that the boundary list is consistent with a closed orientable embedding.

Check Your Understanding

Use the rotations, face boundaries, and edge bounds to justify each answer.

At vertex \(2\) in the \(K_5\) construction, write the prescribed cyclic neighbor order. Then write the face \(F_2\).
In the \(K_5\) construction, how many face-boundary edge occurrences are there in total? Verify the count from the number of faces and from the number of edges.
For the \(K_{3,3}\) construction, determine which face contains the directed step \(a_2\to b_1\), and which face contains the reverse step.
Apply the bipartite surface edge bound to \(K_{3,3}\) at genus zero and state the resulting contradiction.
Explain why the torus constructions alone do not establish that either graph has orientable genus exactly one.