I recently encountered the following exam problem: Given an undirected graph $G := (V,E)$ and a natural number $k \geq 1$, we want to cover as many edges as possible using exactly $k$ vertices. Consider the following Greedy approach: at each step $i \in \{1,\dots,k\}$, add to the partial solution the vertex that covers the most new edges.
To show that this is a 2-approximation, the following hint is given: show that the Greedy solution covers at least $ 1/2 \cdot \max_{S \subseteq V, |S| = k} \text{deg}(v)$ edges.
I tried to show this, but failed. Here is my approach:
Assume our algorithm added the vertices $ x_1, x_2, \dots, x_k \in V $ in this order to its solution. Let $ s_1, s_2, \dots, s_k \in V $ be any $ k $ vertices. It suffices to show that the cost of our solution covers at least $ L := \sum_{i=1}^k \text{deg}(s_i)/2 $ vertices.
We can reorder $ s_1,\dots,s_k $, such that $ s_i \notin \{ x_1,\dots,x_{i-1} \} $ for any $ i $.
Now note that each $x_i$ is chosen with the property that:
$ \begin{equation} \text{deg}(x_i) - |E(\{x_i\},\{x_1,\dots,x_{i-1}\})| \geq \text{deg}(v) - |E(\{v\},\{x_1,\dots,x_{i-1}\})|, \ \\ \forall v \in V \setminus \{x_1,\dots,x_{i-1}\} \end{equation} $
By the special ordering we have for $ s_1,\dots,s_k $, this implies:
$ \begin{equation} \text{deg}(x_i) - |E(\{x_i\},\{x_1,\dots,x_{i-1}\})| \geq \text{deg}(s_i) - |E(\{s_i\},\{x_1,\dots,x_{i-1}\})|\end{equation} $
We obtain:
$ \begin{align} &\sum_{i=1}^k (\text{deg}(x_i) - |E(\{x_i\},\{x_1,\dots,x_{i-1}\})|) \geq \\ &\sum_{i=1}^k (\text{deg}(s_i) - |E(\{s_i\},\{x_1,\dots,x_{i-1}\})|) = \\ & 2 \cdot L - \sum_{i=1}^k |E(\{s_i\},\{x_1,\dots,x_{i-1}\})| \end{align} $
where the LHS is the number of edges covered by the Greedy algorithm. So I'd like to show that:
$ \begin{equation} \sum_{i=1}^k |E(\{s_i\},\{x_1,\dots,x_{i-1}\})| \leq L \end{equation} $
And I'm stuck here.
I am curious how the lower bound of $ 1/2 \cdot \max_{S \subseteq V, |S| = k} \text{deg}(v)$ can be shown, either by continuing my arguments or by an entirely different approach.