Controlling and steering the growth of single walled carbon nanotubes is often believed to require controlling of the nucleation stage. Yet, little is known about the microscopic mechanisms governing the nucleation from hydrocarbon molecules. Specifically, we address here the dehydrogenation of hydrocarbon molecules and the formation of all-carbon graphitic islands on metallic nanoclusters from hydrocarbon molecules under conditions typical for carbon nanotube growth. Employing reactive molecular dynamics simulations, we demonstrate for the first time that the formation of a graphitic network occurs through the intermediate formation of vertically oriented, not fully dehydrogenated graphitic islands. Upon dehydrogenation of these vertical graphenes, the islands curve over the surface, thereby forming a carbon network covering the nanoparticle. The results indicate that controlling the extent of dehydrogenation offers an additional parameter to control the nucleation of carbon nanotubes.