Ground-state structures of supported C clusters, C-N (N = 16, ... , 26), on four selected transition metal surfaces [Rh(111), Ru(0001), Ni(111), and Cu(111)] are systematically explored by ab initio calculations. It is found that the core-shell structured C-21, which is a fraction of C-60 possessing three isolated pentagons and C-3v symmetry, is a very stable magic cluster on all these metal surfaces. Comparison with experimental scanning tunneling microscopy images, dI/dV curves, and cluster heights proves that C-21 is the experimentally observed dominating C precursor in graphene chemical vapor deposition (CVD) growth. The exceptional stability of the C-21 cluster is attributed to its high symmetry, core-shell geometry, and strong binding between edge C atoms and the metal surfaces. Besides, the high barrier of two C-21 clusters' dimerization explains its temperature-dependent behavior in graphene CVD growth.