An upper bound for the Ramsey numbers r(K3,G)

AbstractThe Ramsey number r(H,G) is defined as the minimum N such that for any coloring of the edges of the N-vertex complete graph KN in red and blue, it must contain either a ŕed H or a blue G. In this paper we show that for any graph G without isolated vertices, r(K3,G)⩽2q+1 where G has q edges. In other words, any graph on 2q+1 vertices with independence number at most 2 contains every (isolate-free) graph on q edges. This establishes a 1980 conjecture of Harary. The result is best possible as a function of q