Find a vertex cover of size 20 for the pictured graph

If you don't want to just stumble around blindly until you get there, here's how you find the solution.

The solution you found with $21$ vertices probably looks something like this:

Naive solution

If this is the optimal solution, then there is a perfect matching in which every edge has one endpoint among the chosen vertices. But in fact, if we try to find such a matching, we get irreparably stuck:

Naive solution gets stuck

We started by giving a bunch of vertices an edge, but the purple vertex has no edge to an unused neighbor. There's no way to fix this, because the $11$ vertices we've looked at so far (the $10$ we've given an edge, plus the purple vertex) have only $10$ neighbors... but that's exactly what we want to improve the vertex cover. Just replace these $11$ vertices by their $10$ neighbors, and you get a solution of size $20$:

Improved solution


Must write at least $30$ charcters.

enter image description here

Tags:

Graph Theory