We have prepared composites of polyvinyl acetate (PVAc) reinforced with solution exfoliated graphene. We observe a 50% increase in stiffness and a 100% increase in tensile strength on addition of 0.1 vol % graphene compared to the pristine polymer. As PVAc is commonly used commercially as a glue, we have tested such composites as adhesives. The adhesive strength and toughness of the composites were up to 4 and 7 times higher, respectively, than the pristine polymer.