matching Matching 2002-05-26 03:06:56 2006-09-27 22:55:45 Definition maximal matching perfect matching % this is the default PlanetMath preamble. as your knowledge % of TeX increases, you will probably want to edit this, but % it should be fine as is for beginners. % almost certainly you want these \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsfonts} % used for TeXing text within eps files %\usepackage{psfrag} % need this for including graphics (\includegraphics) %\usepackage{graphicx} % for neatly defining theorems and propositions %\usepackage{amsthm} % making logically defined graphics %\usepackage{xypic} % there are many more packages, add them here as you need them % define commands here Let $G$ be a graph. A \emph{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 \emph{maximal matchings}. A maximal matching on a graph $G$ is simply a matching of the largest possible size. A \emph{perfect matching} is a matching that saturates every vertex.