On a Random Graph with Immigrating Vertices: Emergence of the Giant Component David J. Aldous and Boris Pittel A randomly evolving graph, with vertices immigrating at rate $n$ and each possible edge appearing at rate $1/n$, is studied. The detailed picture of emergence of giant components with $O(n^{2/3})$ vertices is shown to be the same as in the Erd\H{o}s - R\'{e}nyi graph process with the number of vertices fixed at $n$ at the start. A major difference is that now the transition occurs about a time $t=\pi/2$, rather than $t=1$. The proof has three ingredients. The size of the largest component in the subcritical phase is bounded by comparison with a certain multitype branching process. With this bound at hand, the growth of the sum-of-squares and sum-of-cubes of component sizes is shown, via martingale methods, to follow closely a solution of the Smoluchovsky-type equations. The approximation allows us to apply results of Aldous (1997) on emergence of giant components in the multiplicative coalescent, i.e. a non-uniform random graph process.