Unions of bipartite graphs and graphs with bounded degree

Conjecture (proposed by Erdös [1])

For \(n \geq 3\), any graph with \(\binom{2n+1}{2} -\binom{n}{2}-1\) edges is the union of a bipartite graph and a graph with maximum degree less than \( n\).

Faudree proved that every graph on \( 2n+1\) vertices having \( \binom{2n+1}{2} -\binom{n}{2}-1\) edges is the union of a bipartite graph and a graph with maximum degree less than \( n\). The problem remains open when the graph has more than \( 2n+1\) vertices.

Bibliography
1 P. Erdös, Problems and results in graph theory, The theory and applications of graphs (Kalamazoo, MI, 1980), 331-341, Wiley, New York, 1981.