Achei no pdf que o Thadeu Russo me mandou o seguinte teorema: "Seja M um emparelhamento relativamente ao qual não existe caminho aumentante. Seja U' os vértices de U expostos por M. Seja L o conjunto de vértices que podem ser alcançados por algum dicaminho começando num vértice de U'. Então, C = (U \ L) união (W intersecção L) é uma cobertura e |C| = |M|".
Ou seja, com K_U = (U \ L) e K_W=(W intersecção L), dá pra provar o negócio!
Fórum