Mangoes and Blueberries

Dedicated to the memory of Paul Erdős We prove the following conjecture of Erdős and Hajnal: For every integer k there is an f(k) such that if for a graph G, every subgraph H of G has a stable set containing vertices, then G contains a set X of at most f(k) vertices such that G−X is bipartite. This conjecture was related to me by Paul Erdős at a conference held in Annecy during July of 1996. I regret not being able to share the answer with him. Received: August 20, 1997