Question 9: Recall that in the vertex cover problem, we are trying to…

Recall that in the vertex cover problem, we are trying to find a smallest subset $S$ of vertices in a graph $G$ such that $G \setminus S$ is an independent set; in other words, for every edges $(u, v)$ in the graph $G$, we have that $\{u, v\} \cap S$ is non-empty.

Consider the algorithm that repeats the following steps as long as the graph has at least one edge available: select a vertex of maximum degree (say $w$), and include $w$ in the solution; thereafter, delete $w$ and all edges incident to $w$.

Based on the above data, answer the given subquestions.

Is it true that the algorithm always outputs a vertex cover?