Decreasing the maximum average degree by deleting an independent set or a d-degenerate subgraph

Wojciech Nadara, Marcin Smulewicz

The maximum average degree $\mathrm{mad}(G)$ of a graph $G$ is the maximum average degree over all subgraphs of $G$. In this paper we prove that for every $G$ and positive integer…