
Subgraph of large average degree and large girth.
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
.






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.