The order upper bound on parity embedding of a graph (Q1924161)

A graph is said to be parity embedded in a surface \(S\) if it is embedded in \(S\) so that a closed path in the graph preserves or reverses orientation according as its length is even or odd. A compact surface, \(S'\), is larger than another, \(S\), if \(S'\) is obtained from \(S\) by adding any number of crosscaps or handles. In this paper is determined the smallest surface in which \(K^\circ_n\), the complete graph with a loop at each vertex, has a parity embedding. Let \(d(- K^\circ_n)\) denote the crosscap number of this surface. By usual calculations with Euler's formula one obtains the lower bound \(d(- K^\circ_n) \geq \lceil n(n - 3)/4 \rceil + 2\). The main part of the paper is a proof, by induction on \(n\), that equality holds for \(n \geq 6\). The induction proceeds in steps of 4 in two series starting at \(n = 6\) and \(n = 7\), by showing through diagrams how to add at once 4 vertices and their incident edges. The cases \(n \equiv 8, 9 \pmod 4\) are solved by adding 2 or 3 vertices to cases \(n - 2\) or \(n - 3\), respectively. In the remaining cases, \(n \leq 5\), the obvious lower bound is \(n\) due to the \(n\) loops. This is the value of \(d(- K^\circ_n)\) for \(n \leq 4\), but \(d(- K^\circ_5) = 6\), which exceeds both lower bounds. It follows that the smallest surface in which every graph of order \(n\) (possibly with loops or multiple edges) has a parity embedding is the sphere with \(d(- K^\circ_n)\) crosscaps. It also follows that, if \(\widetilde \Gamma\) denotes \(K_{n,n}\) with vertex set \(\{x_1, \dots, x_n, y_1, \dots, y_n\}\) and all edges of the form \(x_iy_i\) doubled, then \(d(- K^\circ_n) - 1\) handles are necessary and sufficient to embed \(\widetilde \Gamma\) antipodally in an orientable surface, i.e., so that some orientation-reversing, involutory, fixed-point-free autohomeomorphism of the embedding surface leaves the embedded \(\widetilde \Gamma\) invariant but interchanges each pair \(x_i\) and \(y_i\).