Graphene grown on metal catalysts with low carbon solubility is a highly competitive alternative to exfoliated and other forms of graphene, yet a single-layer, single-crystal structure remains a challenge because of the large number of randomly oriented nuclei that form grain boundaries when stitched together. A kinetic model of graphene nucleation and growth is developed to elucidate the effective controls of the graphene island density and surface coverage from the onset of nucleation to the full monolayer formation in low-pressure, low-temperature CVD. The model unprecedentedly involves the complete cycle of the elementary gas-phase and surface processes and shows a precise quantitative agreement with the recent low-energy electron diffraction measurements and also explains numerous parameter trends from a host of experimental reports. These agreements are demonstrated for a broad pressure range as well as different combinations of precursor gases and supporting catalysts. The critical role of hydrogen in controlling the graphene nucleation and monolayer formation is revealed and quantified. The model is generic and can be extended to even broader ranges of catalysts and precursor gases/pressures to enable the as yet elusive effective control of the crystalline structure and number of layers of graphene using the minimum amounts of matter and energy.