# Size of maximum matching in bipartite graph

I was wondering if there exists a way to compute the size of the maximum matching in a bipartite graph without having to compute the maximum matching itself. Any help or direction will be really appreciated.

Thank you.

-

## 1 Answer

You could find the minimum vertex cover. According to the König-Egerváry Theorem, the minimum vertex cover is the same size as a maximum matching of any bipartite graph.

-
The algos i looked for finding the minimum vertex cover are all based on first finding the maximum matching. –  dilpreet023 Jul 7 '13 at 5:50
Sorry, I am not familiar then with any algorithm of the sort you are looking for, however the randomized algorithm explained in this paper runs pretty fast. –  Shil B. Jul 7 '13 at 16:49