We present high-resolution angle-resolved photoemission spectroscopy study in conjunction with first principles calculations to investigate how the interaction of electrons with phonons in graphene is modified by the presence of Yb. We find that the transferred charges from Yb to the graphene layer hybridize with the graphene $pi$ bands, leading to a strong enhancement of the electron-phonon interaction. Specifically, the electron-phonon coupling constant is increased by as much as a factor of 10 upon the introduction of Yb with respect to as grown graphene ($leq$0.05). The observed coupling constant constitutes the highest value ever measured for graphene and suggests that the hybridization between graphene and the adatoms might be a critical parameter in realizing superconducting graphene.