Genus of the complete graph of six vertices

Question

A graph is called $\textbf{planar}$ if it can be embedded in the plane. A nonplanar graph can be embedded in some surface obtained from the sphere by attaching some handles or crosscaps. We denote by $\mathbb S_k$ a sphere with $k$ handles and by $\mathbb N_k$ a sphere with $k$ crosscaps. Note that both $\mathbb S_0$ and $\mathbb N_0$ are the sphere itself, and $\mathbb S_1$ and $\mathbb N_1$ are a torus and a projective plane, respectively. The smallest non-negative integer $k$ such that a graph $\Gamma$ can be embedded on $\mathbb S_k$ is called the $\textbf{orientable genus}$ or genus of graph $\Gamma$, and is denoted by $\gamma(\Gamma)$. The $\textbf{nonorientable genus}$ of $\Gamma$, denoted by $\bar{\gamma}(\Gamma)$, is the smallest integer k such that C can be embedded on $\mathbb N$ (see the paper $\textbf{ Power graphs of (non) orientable genus two}$ ).

I have tried to understand the definition of the genus by using the example of a complete graph with six vertices. I know that $\gamma(K_6) = \bar{\gamma}(K_6) = 1$. But I do not know how they are equal to one.

Answer 1

This is a birds-eye view of a torus with $K_6$ embedded on it's surface. You can only see the three vertices on the top of the torus, but I'm sure you can imagine how they connect to the three vertices on the bottom of the torus.

The projective plane can be formed by twisting and gluing opposite sides of a square together. When this square is glued together, all the edges should join up to make a copy of $K_6$.

Answer 2

It is equal to one because it contains $K_5$ and we can exhibit an embedding in genus 1. In general the problem of determining the genus of a graph is NP-hard.

Here is an approach for finding an embedding in orientable genus 1:

Cut out two open disks from the sphere, and straighten it out into a tube, so that what you get is a tube with boundary. Put three vertices $1$, $2$, $3$ on the bottom boundary, and three vertices $A$, $B$, $C$ on the top. You can immediately get the following graph without any edge intersections:

$$1A, 1B, 1C, 12, 2C, 23, 3C,AB,BC$$

We can also go around the tube, so in addition to the edges above we also have

$$13, 3A, AC.$$

Now we have a graph with 12 edges, two vertices $(1, C)$ of degree 5, two vertices (3, A) of degree 4 and two vertices (2, B) of degree 3.

Take now a sphere, trace out two circles on it with the same radius and centers on the north and south pole. Mark three points on the first circle with $123$, and three points on the second circle with $ABC$ so that $1$ and $A$, $2$ and $B$, and $3$ and $C$ are mirror images with respect to the equator. Now glue the tube along the two circles so that the points and the vertices match-up (and remove the interiors of the two circles that contain the poles). It is easy to see that the three missing edges $2A$, $2B$ and $3B$ can be drawn without any interstections.