The precise role of electron-phonon (𝑒−ph) coupling in graphene and related materials on a honeycomb lattice is not yet fully understood, despite extensive research on these systems. Here, we perform sign-problem-free determinant quantum Monte Carlo simulations of the optical Su-Schrieffer-Heeger (oSSH)-Hubbard model on the honeycomb lattice, focusing on the parameters relevant to graphene. Performing finite-size scaling analyzes, we obtain the model’s ground-state phase diagram, which includes the semi-metal (SM), Kekulé valence bond solid (KVBS), and antiferromagnetic (AFM) phases, as well as indications of a small KVBS/AFM coexistence region. We find that a weak to moderate Hubbard repulsion, tuned toward the SM-AFM critical value in the pure honeycomb Hubbard model, enhances KVBS correlations and can even stabilize the KVBS phase. Estimating the effective parameters for graphene places it in the SM region of the phase diagram, but near the SM-KVBS phase boundary. Notably, we predict that increasing either the on-site Hubbard repulsion or the 𝑒−phcoupling strength drives graphene toward the KVBS phase rather than the AFM phase, highlighting a synergistic effect that can be exploited to further control the remarkable properties of graphene and related materials.