MathDB
Graph and degree of vertices - IMO LongList 1992 USA3

Source:

September 2, 2010
combinatoricsgraph theoryExtremal Graph TheoryIMO ShortlistIMO Longlist

Problem Statement

Given a graph with nn vertices and a positive integer mm that is less than n n, prove that the graph contains a set of m+1m+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.m-1.
Back to ProblemsView on AoPS