A matching, also called an independent edge set, on a graph G is a set of edges of G such that no two sets share a vertex in common. It is not possible for a matching on a graph with n nodes to exceed n/2 edges. When a matching with n/2 edges exists, it is called a perfect matching. When a matching exists that leaves a single vertex unmatched, it is called a near-perfect matching. While not all graphs have perfect matchings, a largest matching (commonly known as a maximum matching or maximum independent edge set) exists for every graph. The size of this maximum matching is called the matching number of G and is denoted ν(G).

Berge's theorem | blossom algorithm | Hosoya index | hungarian maximum matching algorithm | independent edge set | marriage theorem | matching-generating polynomial | matching number | matching polynomial | maximal independent edge set | maximum independent edge set | near-perfect matching | perfect matching | stable marriage problem