**The Genus of a Complete
Graph Minus a Hamiltonian Cycle **

Let *K_n** – C_n* denote
the complete graph minus the edges of a Hamiltonian cycle. Art White asks:

**Conjecture:** *What is the orientable genus of *K_n – C_n

The conjectured value would be given by the embedding as close to a
triangulation as possible, namely *ceiling[**(n^2-9n+12)/12]*
(with possible small exceptions). White reports the following observations:

1) the
genus is non-decreasing in *n*

2) the
graph is non-planar for *n* at most 6

3) the
conjectured bound fails for *n = 7*

4) the
conjecture is true for *n = 8,9*

5) current graph constructions may be useful (see [R])

The problem was apparently suggested to Art White by Mike Plummer, but I do
not know why he was interested.

**References: **

[R] G. Ringel, Map Color Theeorem,

Submitted by: Arthur White

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

December, 2003