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
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
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 in $G$.
|show 3 more comments|