The Effect of Edge Deletion on the Nonorientable Genus

The *nonorientable genus* of a graph *G, h(G)*, is the minimum number *h* such that *G* embeds on the surface formed by adding *h* crosscaps to the sphere. It is well-known that the deletion of an edge may lower the nonorientable genus by two, that is, there exists a graph *G* containing an edge *e* such that *h(G-e) = h(G) - 2*.

Rainer Bodendiek asks the following.

**Question:** Does there exist a graph such that the deletion of every edge lowers the nonorientable genus by two?

The negation of this is equivalent to the question: *``Does every graph G have an edge e such that h(G - e) = h(G) - 1?''*

A graph is *irreducible* for a given surface if the graph does not embed on that surface, but every edge-deleted subgraph does so embed. The preceding questions are equivalent to: *``Does there exist a graph which is simultaneously irreducible for two different nonorientable surfaces?''* It is known that for each surface, orientable or nonorientable, the set of graphs without degree two vertices that are irreducible for that surface is finite. Constructive proofs of this employ induction on the genus of the surface. Prof. Bodendiek asserts that if the answer to the first question is no, then the techniques used in [BW] to prove the finiteness of the set of graphs irreducible for orientable surfaces extend to prove the analogous result for nonorientable surfaces.

One approach would be to examine graphs where the automorphism group acts transitively on the edges; this would reduce the difficulty in checking the genus of the edge deleted subgraphs.

I believe that Bruce Richter might have also asked this question in a different context.

**References**

[BW] R. Bodendiek and K. Wagner, Solution to Konig's graph embedding problem *Math. Nachr.* **140** (1989) 251-272

Submitted by: Dan Archdeacon, Department of Math. and Stat., University of Vermont, Burlington, VT, USA 05405

Send comments to *dan.archdeacon@uvm.edu *

August, 1995