erdős #1155
Construct a random graph on vertices in the following way: begin with the complete graph . 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 is the number of edges remaining, then is it true thatand that almost surely?
Worked, still open.
graph theory · open · 0 attempts
use this record
vela registry pull vfr_37aec80d874a0239vela reproduce examples/erdos-problems