Maximum Matchings

Graph Theory · Axiom Academy

Finding the largest possible matching in a graph and the fundamental algorithms to achieve it 1. Maximum Matching Definition A maximum matching is a matching with the largest possible number of edges among all matchings in the graph. The size of a maximum matching is denoted ν(G) (nu of G), called the matching number of the graph. Watch the animation to see how a maximum matching is constructed: 2. Maximal vs. Maximum Matching Maximal: Cannot be extended (local property) Maximum: Largest possible size (global property) Every maximum matching is maximal, but not every maximal matching is maximum. A maximal matching might be suboptimal. Maximal: "I can't add any more edges without violating the matching property" Maximum: "No other matching in this graph has more edges" A graph can have multiple maximal matchings of different sizes All maximum matchings have the same size: ν(G) The animation demonstrates the difference with a concrete example: The key to finding maximum matchings lies in the concept of an augmenting path . Alternates between edges NOT in M and edges in M Has odd length (odd number of edges) Why are augmenting paths important? If we flip the path (remove matched edges, add unmatched edges), we get a larger matching! Watch how an augmenting path increases the matching size: 4. Berge's Theorem (Augmenting Path Theorem) This elegant theorem provides both a characterization of maximum matchings and a foundation for algorithms.

This is the written version of the interactive lesson above. See the full Graph Theory course.