Graphene synthesis on ultra-thin catalysts can allow the use of graphene-coated metal films in electronic applications. Graphene coated thin films are expected to offer superior mechanical performance owing to the strength of graphene. However, several factors need to be considered to assure the stability of thin films at the high temperatures required for graphene synthesis. In this work, we present a systematic framework for the selection of thin films (< 1 micron thickness) to be used as catalyst for graphene synthesis. We present our progress towards the rapid synthesis of graphene at 1100 C in less than two minutes, thus avoiding solid state dewetting. The quality of the graphene is assessed by Scanning Electron Microscopy, Raman spectroscopy and indentation. It is shown that these films exhibit higher stiffness and resistance to crack propagation.