Suppose that a process begins with n isolated vertices, to which edges are added randomly one by one so that the maximum degree of the induced graph is always bounded above by d . We prove that if n → ∞ with d fixed, then with probability tending to 1, the final result of this process is a graph with ⌊ nd / 2⌋ edges.
No takes yet. Share an insight, caveat, or question.
Ruciński et al. (1992) studied this question.