Back

Answers to Matchings

The red dashed edges in these two graphs each form a matching.

However, the second matching is a maximum matching since no more edges can be added. In the first graph, there is at least one more edge that can be added. Can you find a matching in the first graph with more than one more edge?

Note that the one of the lower left edges can be added easily to the matching. However, one can also switch the edges which are in the matching on the lower right half of the graph so that another edge can be added. The following is one possible result:

This is a maximum matching. To see why you can consider how far each vertex is from one of the corner vertices.