Item 4.6.3.a.

Find the largest possible alternating path for the partial matching of your friend's graph. Is it an augmenting path? How would this help you find a larger matching?

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