On spanning trees and walks of low maximum degree (Q2707974)

Let \(\chi\) denote the Euler characteristic of a surface. Given \(\chi\leq -36\), a graph is called \(\chi\)-tree-minimal if it embeds on a surface of Euler characteristic \(\chi\), is 3-connected, has no \([{8-2\chi\over 3}]\)-tree, and is a graph on the fewest edges with this property. Given \(\chi\leq -46\), a graph is called \(\chi\)-walk-minimal if it embeds on a surface of Euler characteristic \(\chi\), is 3-connected, has no light \([{6-2\chi\over 3}]\)-walk, and is a graph on the fewest edges with this property. A graph is called \(\chi\)-minimal if it is either \(\chi\)-tree-minimal or \(\chi\)-walk-minimal. It is shown that no \(\chi\)-minimal graph has a triangle. Most results are proven by means of a generalization of a method of Tutte. But the main result, which states the best possible result that a 3-connected graph embeddable on a surface of Euler characteristic \(\chi\leq- 46\) has a spanning tree of maximum degree at most \([{8- 2\chi\over 3}]\) and a closed, spanning walk meeting at each vertex at most \([{6-2\chi\over 3}]\) times, is proven by means of a method defined here as discharging method. This is a technique developed to solve the 4-color problem. In the final part, an extremal class of well-known graphs, \(K_{3,6-2\chi}\), is mentioned.