A KOTZIG TYPE THEOREM FOR NON-ORIENTABLE SURFACES
Stanislav Jendrol′, Milan Tuhársky · Czech digital mathematics library · 2006
A. Kotzig in 1955 proved that every polyhedral map on the sphere (i.e., a 3-connected plane graph) contains an edge with degree sum of its endvertices at most 13; this bound being sharp.J. Ivanco in 1992 proved an analogue of Kotzig's theorem for graphs of an orientable genus g.In this note it is proved that every simple graph embeddable in a non-orientable surface of genus q and minimum degree > 3 contains an edge e with degree sum w(e) of its endvertices being ( 2o + ll if 1 < q < 2, 2o + 9 if3 6 .All the above bounds are tight.