When trying to find the minimum vertex cover, you’re going to be trying to find the minimum number of vertices that will include all the edges.

We can start with the densest vertex on the graph and hope that we get lucky.

We can choose vertex 3 next. Through some trial and error, you’ll see that you will have to choose 2 points from points 1, 2, and 3 regardless of which point you choose next.

Finally, we must choose either vertex 4 or vertex 6. We’ll choose vertex 4. Since all the edges are now included, this completes the minimum vertex cover. The minimum vertex cover consists of vertices 1, 3, 4, and 5.

If you liked what you read, check out my book, An Illustrative Introduction to Algorithms.