In the Greedy$-$Algorithm lecture one of the exercises considered the following greedy heuristic for

finding a minimum vertex cover. At each step, select the vertex v from Gi having highest degree and

add v to the cover. Then Gi$+1$ is obtained from Gi by removing v and any edge incident with v$.$