Dense graphs without 3-regular subgraphs (Q1892830)

By means of probabilistic constructions the authors show that there are graphs with \(n\) vertices and \(c n\log\log n\) edges that contain no cubic subgraph. On the other hand, for every \(k\) there exists \(c_ k> 0\) such that any graph with maximum degree \(\Delta\) and at least \(c_ k n\log \Delta\) edges contains a \(k\)-regular subgraph. Also related problems are studied.