Find a vertex cover of size 20 for the pictured graph I want to use Konig's theorem to show that the pictured graph $G$ has no perfect matching. By this theorem it suffices to find a vertex cover of size $|G|/2-1= 20$, but so far I have only been able to find vertex covers of size 21. I'm just doing this by inspection as opposed to using any algorithms, and it's not immediately obvious to me how to find a cover of size 20. ![enter image description here](

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](