Matchings Definition

Graph Theory · Axiom Academy

LESSON Formal Definition of Matchings Understanding matchings as edge sets where no two edges share a vertex Given a graph G = (V, E), a matching M is a subset of edges where no two edges share a common vertex. Watch the animation to see how a matching is constructed, ensuring no two edges share vertices: 2. Matched vs Unmatched Vertices In the context of a matching M, we classify vertices based on whether they are incident to an edge in M: Matched Vertex: A vertex v is matched (or saturated) if there exists an edge in M incident to v Unmatched Vertex: A vertex v is unmatched (or unsaturated/exposed) if no edge in M is incident to v The animation demonstrates matched vertices (highlighted) versus unmatched vertices (not covered by the matching): A perfect matching is the ideal scenario where every vertex in the graph is matched. The graph must have an even number of vertices: |V| must be even For a perfect matching M: |M| = |V|/2 Not all graphs have perfect matchings (e.g., graphs with odd |V|) Watch how a perfect matching covers all vertices in the graph: 4. Maximum vs Maximal Matching Two important concepts that are often confused: maximum and maximal matchings are fundamentally different. Every maximum matching is also maximal Not every maximal matching is maximum A maximal matching can have as few as |V|/4 edges in the worst case Compare a maximal (but not maximum) matching with a maximum matching:

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