We have studied large areas of (√3×√3)R30° graphene commensurate with a Pt(111) substrate. A combination of experimental techniques with ab initio density functional theory indicates that this structure is related to a reconstruction at the Pt surface, consisting of an ordered vacancy network formed in the outermost Pt layer and a graphene layer covalently bound to the Pt substrate. The formation of this reconstruction is enhanced if low temperatures and polycyclic aromatic hydrocarbons are used as molecular precursors for epitaxial growth of the graphene layers.