<p>So you are looking for the <a href="http://en.wikipedia.org/wiki/Circumference#Circumference_of_a_graph" rel="nofollow">circumference</a> of a connected cubic bridgeless graph $G$. Since a bridgeless cubic graph is immediately 2-connected, Bondy and Entringer showed in the paper </p>

<blockquote>
  <p><a href="http://books.google.com.tw/books?id=5ECBwmHmuasC&amp;pg=PA1325&amp;lpg=PA1325&amp;dq=%22Longest+cycles+in+2-connected+graphs+with+prescribed+maximum+degree%22&amp;source=bl&amp;ots=zFV_-2UPb3&amp;sig=myUn-5AYipBVdxbTuDeekhbG9j0&amp;hl=zh-TW&amp;ei=7d8rTdyoLY28vgOJheHPCQ&amp;sa=X&amp;oi=book_result&amp;ct=result&amp;resnum=4&amp;ved=0CDUQ6AEwAw#v=onepage&amp;q=%22Longest%20cycles%20in%202-connected%20graphs%20with%20prescribed%20maximum%20degree%22&amp;f=false" rel="nofollow">Longest cycles in 2-connected graphs with prescribed maximum degree</a>,  Canadian Journal of Mathematics, 1980,</p>
</blockquote>

<p>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 <em>Über längste Kreise in regulären Graphen</em> by Lang and Walther, so this is the best possible. </p>

<p>For the reference, see <em><a href="http://www.sciencedirect.com/science?_ob=ArticleURL&amp;_udi=B6WHT-4D7K6GB-6F&amp;_user=10&amp;_coverDate=08/31/1986&amp;_rdoc=1&amp;_fmt=high&amp;_orig=search&amp;_origin=search&amp;_sort=d&amp;_docanchor=&amp;view=c&amp;_acct=C000050221&amp;_version=1&amp;_urlVersion=0&amp;_userid=10&amp;md5=eefd688915604576acdbd85df7988609&amp;searchtype=a" rel="nofollow">Longest cycles in 3-connected cubic graphs</a></em> 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 <a href="http://portal.acm.org/citation.cfm?id=587013" rel="nofollow">efficient algorithm</a> approximately finding a long cycle in $G$.</p>

CC BY-SA 2.5
2011-01-10T03:12:23.907Z
Hsien-Chih the bound you provide is negative for n<256, so for most practical graphs
N27
CC BY-SA 2.5
2011-01-10T03:29:11.390Z
@N27: Oops so you need a bound for small size graphs. Maybe you can put the requirement in your question, and there may be someone who knows the answer. (I have no idea what the bound is when the graph is small, it seems like the result above is for sufficiently large n.)
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2011-01-10T03:33:34.717Z
@Hsien-Chih There is something wrong with this bound obviously, since for 100,000 vertices it gives a cycle of length 30. Maybe they refer to something else in their publication. However, this problem doesn't seem trivial.
N27
CC BY-SA 2.5
2011-01-10T03:50:46.670Z
@N27: I'm not sure if the bound is wrong. There are cubic bridgeless graphs with a large number of nodes with small maximum cycle. Take [this graph](http://cstheory.stackexchange.com/questions/3024/upper-bounds-on-the-length-of-longest-simple-path-in-non-hamiltonian-graph/3026#3026) for example. (This graph may not meet our bound, but it gives intuition.)
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2011-01-11T04:52:26.280Z
@N27: I found the paper with the 2-connected result. Maybe you can take a look at it to see if the bound is correct.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2011-01-11T22:17:20.723Z
@ Hsien-Chih Chang, thanks. Some other time, maybe. Besides I found what I was looking for.
N27
CC BY-SA 2.5
2011-01-12T00:10:46.577Z
@N27: Then maybe you can post it as an answer to your own question and accept it. This is what a Q&A site for! I would like to know the answer to your question. (There's a *self-learner* badge for it!)
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2011-01-12T05:31:27.790Z
@ Hsien-Chih Chang, actually I learned what I wanted from the example of Dr. Eppstein, since what I needed was a counterexample of a cubic bridgeless graph with a max simple cycle of less than n/2 vertices.
N27
CC BY-SA 2.5
2011-01-10T02:58:37.117Z
2011-01-11T04:51:08.120Z
2011-01-11T04:51:08.120Z
Hsien-Chih Chang 張顯之
<p>I would like to ask if anybody knows any result on the least number of edges the <strong>maximum</strong> simple cycle of connected cubic bridgeless graphs, must have. Thanks</p>

<graph-theory><reference-request><co.combinatorics>
Lower bound on maximum simple cycle in connected cubic bridgeless graphs
N27
# Lower bound on maximum simple cycle in connected cubic bridgeless graphs

(Asked by: username_0 on 2011-01-10)

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

**Tags:** graph-theory, reference-request, co.combinatorics

---

## 1 answers

### Answer by username_1 on 2011-01-10. Score: 6 | Accepted answer

So you are looking for the [circumference](http://en.wikipedia.org/wiki/Circumference#Circumference_of_a_graph) 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](http://books.google.com.tw/books?id=5ECBwmHmuasC&pg=PA1325&lpg=PA1325&dq=%22Longest+cycles+in+2-connected+graphs+with+prescribed+maximum+degree%22&source=bl&ots=zFV_-2UPb3&sig=myUn-5AYipBVdxbTuDeekhbG9j0&hl=zh-TW&ei=7d8rTdyoLY28vgOJheHPCQ&sa=X&oi=book_result&ct=result&resnum=4&ved=0CDUQ6AEwAw#v=onepage&q=%22Longest%20cycles%20in%202-connected%20graphs%20with%20prescribed%20maximum%20degree%22&f=false), 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](http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WHT-4D7K6GB-6F&_user=10&_coverDate=08/31/1986&_rdoc=1&_fmt=high&_orig=search&_origin=search&_sort=d&_docanchor=&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=eefd688915604576acdbd85df7988609&searchtype=a)* 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](http://portal.acm.org/citation.cfm?id=587013) approximately finding a long cycle in $G$.

> **Comments:**
> **username_0**: Hsien-Chih the bound you provide is negative for n<256, so for most practical graphs  
> **username_1**: @N27: Oops so you need a bound for small size graphs. Maybe you can put the requirement in your question, and there may be someone who knows the answer. (I have no idea what the bound is when the graph is small, it seems like the result above is for sufficiently large n.)  
> **username_0**: @Hsien-Chih There is something wrong with this bound obviously, since for 100,000 vertices it gives a cycle of length 30. Maybe they refer to something else in their publication. However, this problem doesn't seem trivial.  
> **username_1**: @N27: I'm not sure if the bound is wrong. There are cubic bridgeless graphs with a large number of nodes with small maximum cycle. Take [this graph](http://cstheory.stackexchange.com/questions/3024/upper-bounds-on-the-length-of-longest-simple-path-in-non-hamiltonian-graph/3026#3026) for example. (This graph may not meet our bound, but it gives intuition.)  
> **username_1**: @N27: I found the paper with the 2-connected result. Maybe you can take a look at it to see if the bound is correct.  
> **username_0**: @ Hsien-Chih Chang, thanks. Some other time, maybe. Besides I found what I was looking for.  
> **username_1**: @N27: Then maybe you can post it as an answer to your own question and accept it. This is what a Q&A site for! I would like to know the answer to your question. (There's a *self-learner* badge for it!)  
> **username_0**: @ Hsien-Chih Chang, actually I learned what I wanted from the example of Dr. Eppstein, since what I needed was a counterexample of a cubic bridgeless graph with a max simple cycle of less than n/2 vertices.  

---

