Nonhamiltonian Triangulations with Large Connectivity and Representativity

AbstractIn this paper we show that for eachnthere is a triangulation of an orientable surface which isn-connected,n-representative, and such that every spanning tree contains a vertex of degree at leastn. This also shows that there exist such graphs where any spanning walk must visit some vertex at leastntimes. We show the analogous results for nonorientable surfaces