Small world graphs by iterated local edge formation

We study graphs obtained by successive creation and destruction of edges into small neighborhoods of the vertices. Starting with a circle graph of large diameter we obtain small world graphs with logarithmic diameter, high clustering coefficients, and a fat tail distribution for the degree. Only local edge formation processes are involved and no preferential attachment was used. Furthermore, we found an interesting phase transition with respect to the initial conditions.