The sequential generation of random edge maximalf-graphs as a function off

A graph with no vertex of degree greater thanf is called anf-graph. Anf-graph to which no edge can be added without introducing a vertex of degree greater thanf is called anedge maximal f-graph. We consider the following procedure. Starting withn labeled vertices and no edges, sequentially add edges one at a time so as to obtain at each step a labeledf-graph. At each step, the edge to be added is selected with equal probability from among those edges whose addition would not violate thef-degree restriction. A terminal graph of this procedure is asequentially generated random edge maximalf-graph. LetP(m; n; f) denote the probability that a sequentially generated random edge maximalf-graph of ordern hasm vertices of degree less thanf. The determination of the distributionP(m; n; f) is an open problem posed by P. Erds. We have obtained various insights concerningP(m; n; f). In particular, we conjecture the form ofP(m; n; f) as a function off.