Equating three degrees of graphs

Abstract

In this paper, we prove that, for every graph with at least 5 vertices, one can delete at most 3 vertices such that the subgraph obtained has at least three vertices with the same degree. This solves an open problem of Caro, Shapira and Yuster [Electron. J. Combin. 21 (2014) P1.24].