[v_g]

If I go through the list of edges one by one and push the two vertices of each edge into a Set, at the end wouldn’t I end up with the minimum number of vertices needed to cover the graph?

Most likely I’m not understanding the problem, would appreciate if someone could clarify.

[anonymoushn]

The minimum vertex cover is a minimal set of vertices such that every edge is incident to at least one vertex in the set. For a star graph with 101 nodes and 100 edges, the minimum vertex cover is a set containing 1 vertex. The algorithm in TFA gives a set containing 2 vertices. Your algorithm gives a set containing a bit more than 2 vertices.

[thethirdone]

You only need one of the vertices of an edge to cover that edge.

So in the simplest case of two vertices connected by an edge, your algorithm would generate a set of size 2 instead of the minimum size 1.

[saagarjha]

Your set would contain all the vertices, while you can do better by only including some. For example, think of three vertices in a line with the first and second vertex joined by and edge and the second and third. The “optimal cover” picks the second vertex and covers both edges.