Graph embeddings on nonorientable surfaces

Question

If a finite graph $G$ can be embedded on an orientable surface of genus $n$, does this mean that it can be embedded on a nonorientable surface of genus $n$? Is the converse of this statement true?

Answer 1

As Hugo Manet's comment suggests, nonorientable and orientable genus don't really line up like that. Euler's formula states that

$$|V|-|E|+|F|=\chi(S),$$

where $\chi(S)$ denotes the Euler characteristic of the surface. The Euler characteristic of the sphere with $g$ handles is $2-2g$, but the Euler characteristic of the sphere with $k$ crosscaps is $2-k$. As a result, maybe the smallest case is really about comparing the Klein bottle and the torus, two surfaces with the same Euler characteristic. Both statements have counterexamples (see Ringel, "Non-existence of graph embeddings"):

• $K_7$, the complete graph on 7 vertices, embeds in the torus, but not the Klein bottle.
• $K_8-C_4$, the complete graph on 8 vertices with edges of a 4-cycle deleted, embeds in the Klein bottle, but not the torus.