## You are here

Homematching

## Primary tabs

# 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.

Defines:

maximal matching, perfect matching

Related:

MaximalMatchingminimalEdgeCoveringTheorem, Matching, EdgeCovering, Saturate

Type of Math Object:

Definition

Major Section:

Reference

## Mathematics Subject Classification

05C70*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections

## Attached Articles

## Corrections

perfect matching by mps ✓