The structure of a single layer of graphene on Ru(0001) has been studied using surface x-ray diffraction. A surprising superstructure containing 1250 carbon atoms has been determined, whereby 25 x 25 graphene unit cells lie on 23 x 23 unit cells of Ru. Each supercell contains 2 x 2 crystallographically inequivalent subcells caused by corrugation. Strong intensity oscillations in the superstructure rods demonstrate that the Ru substrate is also significantly corrugated down to several monolayers and that the bonding between graphene and Ru is strong and cannot be caused by van der Waals bonds. Charge transfer from the Ru substrate to the graphene expands and weakens the C-C bonds, which helps accommodate the in-plane tensile stress. The elucidation of this superstructure provides important information in the potential application of graphene as a template for nanocluster arrays.