Bipartite subgraphs

It is shown that there exists a positivec so that for any large integerm, any graph with 2m²edges contains a bipartite subgraph with at least edges. This is tight up to the constantc and settles a problem of Erdös. It is also proved that any triangle-free graph withe>1 edges contains a bipartite subgraph with at least e/2+c e^4/5 edges for some absolute positive constantc. This is tight up to the constantc.Research supported in part by a USA Israeli BSF grant and by the Fund for Basic Research administered by the Israel Academy of Sciences.