Simple cubic graphs with no short traveling salesman tour

Robert Lukoťka, Ján Mazák

Let $tsp(G)$ denote the length of a shortest travelling salesman tour in a graph $G$. We prove that for any $\epsilon >0$, there exists a simple $2$-connected planar cubic graph…