Erdős Problem #559

Let \(\hat{R}(G)\) denote the size Ramsey number, the minimal number of edges \(m\) such that there is a graph \(H\) with \(m\) edges that is Ramsey for \(G\). If \(G\) has \(n\) vertices and maximum degree \(d\) then prove that \[\hat{R}(G)\ll_d n.\] This was disproved for \(d=3\) by Rödl and Szemerédi [RoSz00], who constructed a graph on \(n\) vertices with maximum degree \(3\) such that \(\hat{R}(G)\gg n(\log n)^{c}\) for some absolute constant \(c>0\).