Sign up ×  I would like to ask if anybody knows any result on
the least number of edges the maximum simple cycle of connected
cubic bridgeless graphs, must have. Thanks  share|cite|improve
this question  1 Answer 1  up vote 5 down vote accepted  So you
are looking for the circumference of a connected cubic
bridgeless graph $G$. Since a bridgeless cubic graph is
immediately 2-connected, Bondy and Entringer showed in the paper
Longest cycles in 2-connected graphs with prescribed maximum
degree, Canadian Journal of Mathematics, 1980,  that $G$
contains a cycle of length at least $4 (\log_2 n - \log_2\log_2
n - 5)$. And a graph which meets the bound is provided in the
result Über längste Kreise in regulären Graphen by Lang and
Walther, so this is the best possible.  For the reference, see
Longest cycles in 3-connected cubic graphs by Bill Jackson. If
the graph is 3-connected, then the bound can be improved to
$\Omega(n^c)$ with $c\approx 0.69$, and there are efficient
algorithm approximately finding a long cycle