2. A bipartite graph that doesn\'t have a matching might still have a partial ma

Question

2. A bipartite graph that doesn't have a matching might still have a partial matching. By this we mean a set of edges for which no vertex belongs to more than one edge (but possibly belongs to none). Every bipartite graph (with at least one edge) has a partial matching, so we can look for the largest partial matching in a graph Your "friend" claims that she has found the largest partial matching for the graph below (her matching is in bold). She explains that no other edge can be added, because all the edges not used in her partial matching are connected to matched vertices. Is she correct? in her partial matchirg

Explanation / Answer

No, she is not correct. The bold lines shown on the graph do not have the largest partial matching because we can see that the left out vertices can be covered if the last two pair of opposite vertices gets connectd through cross lines and the first and third pair of vertices similarly and the second pair among themselves through straight line makes the largest partial matching possible.

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.