The proof here is incorrect. The issue is that it doesn't establish that the number of edges processed is less than or equal to the size of the optimal vertex c

The proof here is incorrect. The issue is that it doesn't establish that the number of edges processed is less than or equal to the size of the optimal vertex cover. This is critical and has to do with the fact that we only process edges that aren't already covered. https://www.cl.cam.ac.uk/teaching/1415/AdvAlgo/lec8_ann.pdf https://www.cl.cam.ac.uk/teaching/1415/AdvAlgo/lec8_ann.pdf contains a more correct proof. Note the |C∗| ≥ |A| line on slide 8. That's critical to the correctness of the proof, but missing in this article.