Item 4.6.3.b.

Find the largest possible alternating path for the partial matching below. Are there any augmenting paths? Is the partial matching the largest one that exists in the graph?

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