OPEN
This is open, and cannot be resolved with a finite computation.
Construct a random graph on $n$ vertices in the following way: begin with the complete graph $K_n$. At each stage, choose uniformly a random triangle in the graph and delete all the edges of this triangle. Repeat until the graph is triangle-free.
Describe the typical parameters and structure of such a graph. In particular, if $f(n)$ is the number of edges remaining, then is it true that\[\mathbb{E}f(n)\asymp n^{3/2}\]and that $f(n) \ll n^{3/2}$ almost surely?
A problem of Bollobás and Erdős, described in
[Va99] as 'motivated by the task of generating a random triangle-free graph'. In
[Bo98] it says they asked this at the 'Quo Vadis, Graph Theory?' conference in Fairbanks, Alaska, in 1990, 'while admiring the playful bears'.
Grable
[Gr97] proved that, for every $\epsilon>0$,\[\mathbb{P}(f(n)>n^{7/4+\epsilon})\to 0.\]Bohman, Frieze, and Lubetzky
[BFL15] proved that $f(n)=n^{3/2+o(1)}$ almost surely - in other words, for every $\epsilon>0$,\[\mathbb{P}(n^{3/2-\epsilon}<f(n)<n^{3/2+\epsilon})\to 1.\]
View the LaTeX source
This page was last edited 25 January 2026.
Additional thanks to: Jake Mallen
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #1155, https://www.erdosproblems.com/1155, accessed 2026-03-01
