It is known that for triangle-free graphs, if they are $d$-regular, then $2d\leq n$, where $n$ is the number of vertices. In words, the degree is less than or equal to the half of the number of vertices (complete bipartite for $2d = n$).

My question is, for every graph with $2d\leq n$, can we always find a triangle-free graph? Do you know any related results in the literature?

moderation. $\endgroup$ – Todd Trimble♦ Sep 12 '13 at 13:18