Reducing the maximum degree of a graph by deleting edges

Abstract

We investigate the smallest number λe(G) of edges that can be removed from a non-empty graph G so that the resulting graph has a smaller maximum degree. We prove that if m is the number of edges, k is the maximum degree, and t is the number of vertices of degree k, then λe(G) ≤ m+(k−1)t /2k−1. We also show that λe(G) ≤ m k if G is a tree. For each of these two bounds, we determine the graphs which attain the bound. We provide other sharp bounds for λe(G), relations with other graph parameters, and structural observations.