Settling the nonorientable genus of the nearly complete bipartite graphs (Q6133666)

The genus and nonorientable genus for complete and complete bipartite graphs have been known since the 1960s, the formula for the complete case having been conjectured by Heawood in the 19th century. A graph is nearly complete bipartite if it is obtained from a complete bipartite graph by deleting a set of independent edges. The genus of each such graph is known, and the nonorientable genus was known unless the sizes of the parts differ by at most 1 and the set of removed edges is as large as possible (and, in the case that the sizes differ, the larger size is odd). The nonorientable case is a result of \textit{B. Mohar} [Discrete Comput. Geom. 3, No. 1--2, 137--146 (1988; Zbl 0628.05026)]. This paper deals with these missing cases. This is equivalent to showing that the graphs in question have a nonorientable quadrangular embedding. The main argument uses diamond sums. The diamond sum of two quadrangular embeddings of graphs removes a vertex of degree \(d\) in each, leaving a \(2d\)-gon, and then identifies corresponding neighbours of the two removed vertices to create a band of \(d\) new quadrangular faces. Provided at least one of the original embeddings was nonorientable, so is the result. The construction given starts with a suitable complete bipartite graph and repeatedly takes a carefully chosen diamond sum with a very unbalanced nearly complete bipartite graph. This deals with the cases above where the parts differ in size or have equal and even size. The final case (when the parts are equal and odd) is expressed as a Cayley graph, and different methods arising from current graphs are used. A preprint by \textit{S. Lv} [``Constructing nonorientable genus embedding of complete bipartite graph minus a matching'', Preprint, \url{arXiv:2305.10008}] obtained the same results independently using different methods.