Spanning Trees with Small Degrees

Whitney [W] showed that every 4-connected plane triangulation has a Hamiltonian path. This result is not true in general, as there are 4-connected triangulations of other surfaces that are not Hamiltonian. For example, take a 4-connected quadrangulation with more faces than vertices. Add a new vertex in each face and connect it to the four vertices on that face's boundary. The result is a 4-connected triangulation where the new vertices form an independent set. Since there are more new vertices than old, the graph is non-Hamiltonian.

A Hamiltonian path is a spanning tree of maximum degree 2. A relaxation is to search for spanning trees of small maximum degree. This search is helped if the embedded graph is locally planar. We measure this local planarity by the *face-width*, the minimum value of *C* intersect *G* taken over all noncontractible cycles *C* in the surface. Ellingham and Gao [EG] proved that every 4-connected graph embedded with sufficiently large face-width has a spanning tree of maximum degree at most 3. (The ``sufficiently large face-width'' depends on the genus of the surface.) The following conjectures that the number of degree-three vertices is not too large.

**Conjecture:** *Let *G *be a 4-connected graph embedded in a surface of genus* g *with sufficiently large face-width. Then* G *contains a spanning tree with maximum degree 3 such that the number of vertices of degree 3 is *O(g).

Mark Ellingham has written a survey article on results relating face-width, connectivity, and spanning trees [E]. I recommend it for additional background.

References:

[E] M. Ellingham, Spanning paths, cycles, trees, and walks for graphs on surfaces, *Congressus Numerantium* **115** (1996) 55-90.

[EG] M. Ellingham and Z. Gao, Spanning trees in locally planar triangulations, submitted.

[W] H. Whitney, A theorem on graphs, *Ann. of Math.* **32** (1931) 378-390.

Submitted by: Bojan Mohar, Department of Mathematics, University of Ljubljana, Jadranska 19, 61111 Ljubljana, Slovenia.

Send comments to *dan.archdeacon@uvm.edu* and to *bojan.mohar@uni-lj.si*

August, 1995