![](/files/happy5.png)
Conjecture For all positive integers
and
, there exists an integer
such that every graph of average degree at least
contains a subgraph of average degree at least
and girth greater than
.
![$ g $](/files/tex/4239ee4145983e1d8ad375f0606cc7140bce36a3.png)
![$ k $](/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png)
![$ d $](/files/tex/aeba4a4076fc495e8b5df04d874f2911a838883a.png)
![$ d $](/files/tex/aeba4a4076fc495e8b5df04d874f2911a838883a.png)
![$ k $](/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png)
![$ g $](/files/tex/4239ee4145983e1d8ad375f0606cc7140bce36a3.png)
This conjecture is true for regular graphs as observed by Alon (see [KO]). The case was proved in [KO].
Bibliography
[KO] D. Kühn and D. Osthus, Every graph of sufficiently large average degree contains a C4-free subgraph of large average degree, Combinatorica, 24 (2004), 155-162.
*[T] C. Thomassen, Girth in graphs, J. Combin. Theory B 35 (1983), 129–141.
* indicates original appearance(s) of problem.