Longest paths in 2-edge-connected cubic graphs

Abstract

We prove almost tight bounds on the length of paths in $2$-edge-connected cubic graphs. Concretely, we show that (i) every $2$-edge-connected cubic graph of size $n$ has a path of length $\Omega \left(\frac{{\log }^{2}n}{\log \log n}\right)$, and (ii) there exists a $2$-edge-connected cubic graph, such that every path in the graph has length $O({\log }^{2}n)$.