Random Graph Processes with Degree Restrictions

Source abstract

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.