Exactly solvable model of a coalescing random graph

An initially empty (no edges) graph of order M evolves by randomly adding one edge at a time. This edge connects either two linked components and forms a new component of larger order (coalescence of graphs) or increases (by one) the number of edges in a given linked component (cycling). Assuming that the vertices of the graph have a finite valence (the number of edges connected with a given vertex is limited) the kinetic equation for the distribution of linked components of the graph over their orders and valences is formulated and solved by applying the generating function method. The evolution process is shown to reveal a phase transition: the emergence of a giant linked component whose order is comparable to the total order of the graph. The kinetics of growth of this component is studied for arbitrary initial conditions. Found are the time dependences of the average order and the valence of the giant component. The distribution over orders and valences of the linked components of the graph is derived for an initially empty graph comprising M bare polyvalent vertices.