21 Emparejamientos

Vocabulario:

emparejamiento	$M\subset E$ y $\forall e,f\in M: e\cup f=\emptyset$, es decir,
	pares de aristas no tienen vértices en común
perfecto	$M$ cubre todos los vértices de $G$
$M$-alternado	un camino en $G$ alternando con arista de $M$
$M$-aumento	camino $M$-alternado que se puede aumentar

Teorema (Berge):

emparejamiento $M$ es máximo $\qquad\Longrightarrow\qquad$ $G$ no contiene caminos $M$-aumento

Teorema (Hall), teorema del matrimonio:

Sea $G=(U\cup V,E)$ un grafo bipartido. $G$ tiene un emparejamiento completo (para $U$) $\qquad\Longrightarrow\qquad$ $\forall S\subseteq U: \vert N(S)\vert\geq \vert S\vert$, siendo $N(S)$ conjunto de vecinos de $S$.