Edge-maximal graphs on orientable and some non-orientable surfaces

Abstract

We study edge-maximal, non-complete graphs on surfaces that do not triangulate the surface. We prove that there is no such graph on the projective plane ${\mathbb{N}}_1$, $K_7-e$ is the unique such graph on the Klein bottle ${\mathbb{N}}_2$ and $K_8-E(C_5)$ is the unique such graph on the torus ${\mathbb{S}}_1$. In contrast to this for each $g\ge 2$ we construct an infinite family of such graphs on the orientable surface ${\mathbb{S}}_g$ of genus $g$, that are $\lfloor \frac{g}{2}\rfloor$ edges short of a triangulation.

18 pages, 19 figures