  We consider the Densest-Subgraph problem, where a graph and an integer k is
given and we search for a subgraph on exactly k vertices that induces the
maximum number of edges. We prove that this problem is NP-hard even when the
input graph has maximum degree three.
