matching

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 incident 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