Density functional theory (DFT) and semiempirical tight-binding (TB) methods have been used to study the mechanism of graphene growth in the presence and absence of a catalytic surface. Both DFT and TB geometry optimized structures relevant to graphene growth show that the minimum energy growth mechanism is via the sequential addition of carbon hexagons at the edge of the graphene sheet. Monte Carlo (MC) simulations based on the TB model show that defect-free graphene sheets can be grown provided one has the proper combination of temperature, chemical potential, and addition rate. In this work, growth of perfect graphene structures has been simulated at the atomic level. Comparison of the growth mechanism in the absence and presence of a nickel catalyst surface shows that the catalyst (i) allows for adsorption of carbon atoms at surface and subsurface sites, (ii) enables formation of long, stable strings of carbon atoms, and (iii) stabilizes small flakes of graphene that can act as precursors to subsequent growth.