On 2-connected spanning subgraphs with low maximum degree (Q1127880)

Given a graph \(G\), let a \(k\)-trestle of \(G\) be a 2-connected spanning subgraph of \(G\) of maximum degree at most \(k\). Also, let \(\chi(G)\) be the Euler characteristic of \(G\). This paper shows that every 3-connected graph \(G\) has a \((10-2\chi(G))\)-trestle. If \(\chi(G)<-4\), this is improved to \(8-2\chi(G)\), and for \(\chi(G)<-9\), this is further improved to \(6-2\chi(G)\). This result is shown to be best possible for almost all values of \(\chi(G)\) by the demonstration of 3-connected graphs embedded on each surface of Euler characteristic \(\chi<1\) which have no \((5-2\chi)\)-trestle. Also, it is shown that a 4-connected graph embeddable on a surface with non-negative Euler characteristic has a 3-trestle, approaching a conjecture of Nash-Williams.