Highly uniform and crystalline ultradisperse Pt nanoparticles with average sizes of 2.4 nm were deposited on oxygen-free few-layer graphene (FLG) by polyol reduction method without any additional protective agents. The samples were analyzed by Raman spectroscopy, photoelectron spectroscopy using synchrotron radiation and high-resolution transmission electron microscopy. The experiments showed that metal nanoparticles were mostly stabilized at defect sites of the FLG support in the absence of oxygen functionalities. Catalytic properties of the samples were tested in CO oxidation reaction. For Pt nanoparticles forming agglomerates an oscillatory behavior under catalytic reaction conditions was observed for the first time for metal-graphene catalysts.