Exercise 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?

A bipartite graph with ten vertices in two sets of five. Call the top vertices a, b, c, d, e and the bottom vertices 1, 2, 3, 4, 5. Then the graph has the following edges: a-1, a-3, b-1, b-2, c-1, c-2, c-4, d-5, e-4, and e-5. Of these, the edges a-1, b-2, c-4, and e-5 are highlighted bold
in-context