How can I find out an induced subgraph of k nodes with at least m*k*(k-1)/n*(n-1) edges

I am required to use a greedy algorithm to resolve this problem (here m is the number of edges and n is the number of vertices in the original graph). Intuitively´╝î I know it is somehow about density of graph (due to m/n*(n-1) part), so I try to use greedy algorithm to remove the vertex with minimum degree each iteration until I get a k nodes graph, but I don't know how can I GARUNTEE the algorithm give me the final graph with at least m*k*(k-1)/n*(n-1) edges.

Looking for any hints, Thanks.

Answers


Let's define the density of a graph p=m/(n*(n-1)) (for undirected graph it should be p=2*m/(n*(n-1)). Note that for a graph with density p and k vertices, it has (k*(k-1)) * p edges. Also note that when you greedily remove a vertex with the minimum degree, it won't decrease the density of the graph (will proof it below). So when you get the subgraph with k vertices, its density is equal to or greater than m/(n*(n-1)), then the subgraph contains at least k*(k-1)(m*/n*(n-1)) edges.

Let G be a graph with m edges and n vertices, then p=m/n. Let d the minimum degree of all vertices. then we have n * d <= m i.e., d <= m/n. So when you remove the vertex with the minimum degree, you get a graph with m-d edges and n-1 vertices, then the density of the new graph will be p'=(m-d)/(n-1) >= (m-m/n)/(n-1) = m/n = p. So we have that the greedy algorithm won't decrease the density of a graph.


Need Your Help