Which theorem gives the relation between the minimum vertex cover and maximum matching?

M

Mr. Dubey

🎓 Coach ⭐ 103.11K Points

📊 Design and Analysis of Algorithms

Q. Which theorem gives the relation between the minimum vertex cover and maximum matching?

(A) konig’s theorem
(B) kirchhoff’s theorem
(C) kuratowski’s theorem
(D) kelmans theorem

💬 Discuss

✅ Correct Answer: (A) konig’s theorem

Explanation: the konig’s theorem given the equivalence relation between the minimum vertex cover and the maximum matching in graph theory. bipartite graph has a size of minimum vertex cover equal to maximum matching.

Explanation by: Mr. Dubey

the konig’s theorem given the equivalence relation between the minimum vertex cover and the maximum matching in graph theory. bipartite graph has a size of minimum vertex cover equal to maximum matching.

💬 Discussion

📊 Question Analytics

👁️

721

Total Visits

📽️

3 y ago

Published

🎖️

Mr. Dubey

Publisher

📈

86%

Success Rate