# Making a triangle-free graph bipartite

There are many problems on triangles and triangle-free graphs in the problem paper [1]. The following problem was proposed in 1988.

# A problem on making a triangle-free graph bipartite (proposed by Erdös, Faudree, Pach and Spencer [3])

Is it true that every triangle-free graph on $$5n$$ vertices can be made bipartite by deleting at most $$n^2$$ edges?

This conjecture, if true, would be best possible, as can be seen by considering the construction of a $$5$$-partite graph with vertex sets $$S_i$$, $$i = 1, \ldots, 5$$, on $$n$$ vertices each, and putting complete bipartite graphs between $$S_i$$ and $$S_{i+1}$$ where the index addition is taken modulo $$5$$.

Erdös, Györi and Simonovits [2] proved this conjecture for graphs with at least $$5n^2$$ edges. However, the general conjecture is still open for graphs with $$e$$ edges for $$2n^2 < e \leq 5 n^2$$.

Bibliography
1 P. Erdös, Some problems on finite and infinite graphs, Logic and combinatorics (Arcata, Calif., 1985), Contemp. Math. 65, 223-228, Amer. Math. Soc., Providence, R. I., 1987.

2 P. Erdös, E. Györi and M. Simonovits, How many edges should be deleted to make a triangle-free graph bipartite?, Sets, graphs and numbers (Budapest, 1991), Colloq. Math. Soc. János Bolyai, 60, 239-263, North-Holland, Amsterdam, 1992.

3 P. Erdös, R. Faudree, J. Pach and J. H. Spencer, How to make a graph bipartite, J. Comb. Theory Ser. B 45 (1988), 86-98.