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