In 1983 C. Thomassen [8] conjectured that for every k, g ∈ N there exists d such that any graph with average degree at least d contains a subgraph with average degree at least k and girth at least g. A result of Pyber, Szemerédi, and the second author implies that the conjecture is true for every graph G with average d(G) ck,g log(G).
展开▼
