Avoiding 7-circuits in 2-factors of cubic graphs (Q470948)

Summary: Let \(G\) be a cyclically 4-edge-connected cubic graph with girth at least 7 on \(n\) vertices. We show that \(G\) has a 2-factor \(F\) such that at least a linear amount of vertices is not in 7-circuits of \(F\). More precisely, there are at least \(n/657\) vertices of \(G\) that are not in 7-circuits of \(F\). If \(G\) is cyclically 6-edge-connected then the bound can be improved to \(n/189\). As a corollary we obtain bounds on the oddness and on the length of the shortest travelling salesman tour in a cyclically 4-edge-connected (6-edge-connected) cubic graph of girth at least 7.