Minimum Vertex Cover On A Bipartite Graph

Question

Let’s say you have a bipartite graph G = (V, U, E)

v1 is connected to u1, u2, and u3

v2 is connected to u2 and u3

v3 is connected to u3.

By looking at the graph, I know that the minimum vertex covers are {v1, v2, u3} and {v1, u2, u3}, but I’m not sure how to use the bipartite matching/vertex cover algorithm to find this out. Here and Here

When I perform algorithm by hand, the output is just the trivial minimum vertex cover, all of V. Am I doing something wrong?

Edit:

The maximum matching for the graph are the edges (v1, u1), (v2, u2), and (v3, u3). Given the maximum matching, the next step is to start at an unsaturated vertex (a vertex that is not one of the endpoints of a matched edge)

But in this case all the vertices are saturated, so I don't know how to proceed.

Answer 1

Konig's theorem has two directions. The easy direction, corresponding to weak linear programming duality, is that the vertex cover is at least as large as the matching. This is because, in every vertex cover, each matching edge has at least one of its endpoints present.

The hard direction of Konig's theorem, corresponding to strong LP duality, is that there exists a vertex cover where at most (i.e., exactly) one endpoint of each matching edge is present. The thrust of Wikipedia's current proof is to use the matching to construct a vertex cover greedily, showing that, if this algorithm gets stuck, then the allegedly maximum matching has an augmenting path (a contradiction). Every edge is incident to a matched vertex, so the unmatched vertices can be excluded from the cover. Their neighbors in turn must be included. Their neighbors' neighbors can be excluded, etc.

You've noticed that this process sometimes fails to determine the status of each vertex. For this case, the Wikipedia editors write "If there is no such vertex, but there remain vertices not included in any previously-defined set Sk, arbitrarily choose one of these and let S2j+1 consist of that single vertex." One way to justify this step is as follows. Letting u be the chosen vertex and v be u's mate, we're pretending as though v's mate was not u but a newly created vertex u'. Then u is unmatched, so we reseed the algorithm by excluding u and cover the newly created edge u' -- v when we subsequently include v.