The proof here is not incorrect; it does not make any claims on performance. Usually you’d care that your algorithm is not exponential, but here the claim was that this algorithm provides some approximation that is within a constant factor of the optimal solution in terms of the number of vertices it picks.