Maximize the number of edges in subgraph
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.