Is this example with konigs bipartite graph theorem correct? [closed]

Question

Closed. This question needs details or clarity. It is not currently accepting answers.

---

Want to improve this question? Add details and clarify the problem by editing this post.

Closed 9 years ago.

Improve this question

Take example:-

Connections:

1 - 1"

1 - 2"

2 - 2"

2 - 3"

3 - 3"

3 - 4"

4 - 4"

According to konigs theorem maximal matching gives minimum vertex cover but here:

(1-1",2-3",4-4") gives answer 3 with minimum vertex cover while (1-1",2-2",3-3",4-4") maximum matching gives answer 4.

What am i doing wrong in this.... Please help....

Answer 1

In the vertex cover problem, you want to pick set of vertices V in such a way that every edge in the graph has at least one endpoint in V.

Konig's theorem is the following:

In any bipartite graph, the number of edges in a maximum matching equals the number of vertices in a minimum vertex cover.

In your example, maximum matching is of course 4, but also minimum vertex cover is 4 because you can cover all edges by picking vertices {1, 2, 3, 4} and you cannot do better than that.