Teorema de Emparelhamento de König

A maior cardinalidade de um emparelhamento num grafo bipartido $G$ é a menor cardinalidade de um conjunto de vértices que cobre as arestas.

Demonstração:

Considere um grafo $G=(V,E)$ bipartido, com bipartição $\{A,B\}$. Seja $M$ um emparelhamento de $G$ de máxima cardinalidade. Para toda aresta de $M$, escolheremos uma de suas extremidades: o vértice em $B$, se existe um caminho alternante que termina ali, e caso contrário, escolhemos seu vértice em $A$. Chamaremos o conjunto desses vértices de $U$.

Perceba que qualquer conjunto de vértices que cobre $E$ deve também cobrir $M$, ou seja, a cardinalidade mínima de tal conjunto é $|M|$. Como $|U|=|M|$, basta mostrar que $U$ cobre $E$. Observe, também, que se algum caminho alternante termina em $b\in B$, então $b\in U$, pois caso contrário teríamos um caminho ampliador, contrariando a hipótese que $M$ é de tamanho máximo.

Com $a\in A$ e $b\in B$, seja $ab\in E$ uma aresta qualquer. Se $a\in U$, terminamos. Caso contrário, é suficiente mostrar que existe algum caminho alternante que termina em $b$. Com $a\notin U$, ou $a$ está emparelhado ou não está. Se não estiver, $ab$ é um caminho alternante que acaba em $b$, e terminamos. Se $a$ estiver emparelhado, então existe $b'\in B$ tal que $ab'\in M$. Como $a\notin U$, existe um caminho alternante $P$ que termina em $b'$. Se $b$ está nesse caminho, tome $Pb$, e terminamos. Se não está, tome $Pb'ab$, um caminho alternante que termina em $b$, e assim terminamos.

$\square$