Given a 3-connected graph G, a k-trestle is a 2-connected spanning subgraph of G of maximum degree k. Thus a Hamilton cycle is a 2-trestle. Trestles were originally studied by Barnette who was interested in determining the structure of 3-connected planar graphs (they are not Hamiltonian in general). He proved that they had 15-trestles, and conjectured that they had 6-trestles, which he showed would be the best possible. Gao solved this problem (I do not have the reference), showing that not only do 3-connected plane graphs have 6-trestles, but 3-connected projective plane, torus, and Klein bottle graphs do as well. He used the technique of bridges.

For surfaces of Euler characteristic chi at most negative 10, Sanders and Zhao showed the best possible result that 3-connected graphs embeddable on these surfaces have (6-2chi)-trestles. They used the Discharging Method. For the remaining surfaces, upper bounds were obtained of 8-2chi for surfaces with chi between -9 and -5, and 10-2chi for chi between -1 and -4. The lower bound of 6-2chi is expected to be best possible.

Problem: Settle the problem for the remaining thirteen surfaces.

Similar results can be obtained for higher connectivity. In particular, Nash-Williams conjectured that 4-connected toroidal graphs have 2 -trestles (i.e., are Hamiltonian). Sanders and Zhao showed that every 4-connected graph of Euler characteristic at least zero has a 3-trestle. Duke showed that connectivity high enough guarantees a 2-trestle for every surface.

Problem: Find interesting best possible results for different values of connectivity and k.

Submitted by: Daniel Sanders, Department of Mathematics, The Ohio State University, Columbus, OH 43210 USA. [[Note added by Dan Archdeacon: Dan Sanders has since moved. I do not have his current address.]]

Send comments to dan.archdeacon@uvm.edu