Proofs in Computer Science (Optional) · Certificates
Lesson 7
Nikolai Chukhin · Alexander S. Kulikov
König's theorem guarantees that in a bipartite graph, the size of the maximum matching is equal to the size of the minimum vertex cover. Therefore, it is sufficient to present a vertex cover of size six for this graph.
/Certificates=6/image0.png)
In fact, we do not use the above theorem “to its full extent” here: we only use the fact that the size of any vertex cover in a bipartite graph is not less than the size of any matching. Indeed, if there were a matching of size seven in this graph, then the marked six vertices could not cover it. At the same time, it is interesting to note that known algorithms simultaneously find both the maximum matching and the minimum vertex cover. In other words, along with the answer, they provide a certificate of its optimality!