Graphs that Quadrangulate both the Torus and Klein Bottle

A quadrangulation of a surface S is an embedded graph G such that every face is of size 4. A diamond 2-curve is a curve C in S such that C intersects the quadrangulation in a pair of vertices {x,y}. Hence all but two points on the curve lie in the interior of two faces xayb, ycxd. If C is non-contractible, then it is called an essential diamond 2-curve.

If G quadrangulates S and has an essential diamond 2-curve, then it is easy to cut along this curve and re-imbed G so that it quadrangulates the Klein bottle (this embedding has faces xayd and xcyb). Nakamoto conjectures that this sufficient condition is necessary:

Conjecture:  If G is a graph that has a quadrangular embedding in the torus, then G has a quadrangular embedding in the Klein bottle if and only if the toroidal embedding has an essential diamond 2-curve.

Nakamoto [N] has proven this conjecture for 4-regular graphs.


[N] A. Nakamoto, Four-regular graphs which quadrangulate both the torus and the Klein bottle, (preprint).

Submitted by: Dan Archdeacon (with thanks to Atsuhiro Nakamoto

Send comments to

November, 2003