The adsorption of CO on Pt4 clusters supported on graphene with lattice vacancies is studied theoretically using the first-principles calculation. Our results show that the electronic structure of the graphene-supported Pt4 clusters is significantly modified by the interaction with carbon dangling bonds. As a result the adsorption energy of CO at a Pt site decreases almost linearly with the lowering of the Pt d-band center, in analogy with the linear law previously reported for CO adsorption on various Pt surfaces. An exceptional behavior is found for Pt4 supported on graphene with a tetravacancy, where CO adsorption is noticeably weaker than predicted by the shift in the d-band center. Detailed electronic structure analyses reveal that the deviation from the linear scaling can be attributed to lack of Pt d states near the Fermi level that hybridize with CO molecular orbitals. The weakening of CO adsorption on the Pt4 clusters is considered as a manifestation of the support effect of graphene, and leads to the enhancement of CO poisoning tolerance that is crucial for developing high-performance Pt cluster catalysts.