> E 23.15 Seja G um grafo (U,W)-bipartido.
> Suponha que |U| = |W| e m(G) > (k - 1) |U|
> para algum k inteiro positivo. Prove que G
> tem um emparelhamento de cardinalidade k.
Seja M um emparelhamento máximo e
suponha por um momento que |M| < k.
De acordo com o teorema de König,
G tem uma cobertura K tal que |K| < k.
Logo, m <= |U||K| <= |U|(k-1).
Contradição.
Fórum