Maximize the number of edges in subgraph We are given a graph $G=(V,E)$ and we want an algorithm to find a set of vertices $U$ to maximize the following quantity : $\frac{|E(U)|}{|U|}$ where $E(U)$ denotes the number of edges in the subgraph made with vertex set $U$.
Your problem is known as densest subgraph. According to Wikipedia, there is a polynomial time algorithm based on flow networks, due to Goldberg. See Goldberg's technical report Finding a maximum density subgraph.