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