Let G be a graph. A matching M on G is a subset of the edges of G such that each vertex in G is incidentMathworldPlanetmathPlanetmathPlanetmath with no more than one edge in M.

It is easy to find a matching on a graph; for example, the empty set will always be a matching. Typically, the most interesting matchings are maximal matchings. A maximal matching on a graph G is simply a matching of the largest possible size.

A perfect matching is a matching that saturates every vertex.

Title matching
Canonical name Matching
Date of creation 2013-03-22 12:40:00
Last modified on 2013-03-22 12:40:00
Owner Mathprof (13753)
Last modified by Mathprof (13753)
Numerical id 7
Author Mathprof (13753)
Entry type Definition
Classification msc 05C70
Related topic MaximalMatchingminimalEdgeCoveringTheorem
Related topic Matching
Related topic EdgeCovering
Related topic Saturate
Defines maximal matching
Defines perfect matching