Suppose that we are given an undirected graph, and we know that the maximum edges covered by $k$ vertices is $n$. If we let the greedy algorithm choose these $k$ vertices for us, I am told that it is capable of covering at least $n/2$ edges. Is there a way to prove this? If so, how should it be done?
Since the greedy algorithm removes the vertex with the maximum degree still left in the original graph (along with its incident edges) in each iteration, is it possible to find a connection between the minimal number of edges removed each time by the greedy algorithm to the optimal solution $n$?
I am truly clueless about how such a problem should be solved.
Hints or references are both welcome. Many thanks.