IMO 1992 LL USA80

Given a graph with n vertices and a positive integer m that is

imolonglistmathematicsolympiad

IMO 1992 LL USA80

Origin: USA

Problem

Given a graph with n vertices and a positive integer m that is less than n, prove that the graph contains a set of m + 1 vertices in which the difference between the largest degree of any vertex in the set and the smallest degree of any vertex in the set is at most m −1.