Let $G = (V,E)$ be a simple loop-less graph. The circumference refers to the length of the largest cycle of $G$. The average degree is $avg(G) = |E|*2 / |V|$. I conjecture that if the avg(G) > 2, then $circum(G) > avg(G)$.
I can prove that the circumference is larger than the minimum degree of G. This can be quite easily seen by looking at the maximum path of $G$. The neighbors of the endpoints must then all lie within the path. Connecting one endpoint with it's neighbor that lies the furthest on the path would then result in a cycle of at least the degree of the endpoint + 1.
Any idea how to prove my stronger claim?, or a counter-example?
This is the Erdős-Gallai theorem: a graph with $n$ vertices and more than $\frac12 (k-1)(n-1)$ edges has a cycle of length at least $k$.
(In particular, a graph with average degree $k$ has at least $\frac12 kn > \frac12(k-1)(n-1)$ edges.)