Reducing the maximum degree of a graph by deleting vertices

Abstract

We investigate the smallest number λ(G) of vertices that need to be removed from a non-empty graph G so that the resulting graph has a smaller maximum degree. We prove that if n is the number of vertices, k is the maximum degree, and t is the number of vertices of degree k, then λ(G) ≤ n+(k−1)t /2k . We also show that λ(G) ≤ n k+1 if G is a tree. These bounds are sharp. We provide other bounds together with structural observations.