O enunciado está certo?
Tome G um grafo bipartido que tenha um emparelhamento perfeito. Como não existe um caminho M-aumentador, então M é um tal emparelhamento perfeito. Assim U' = W' = vazio. Portanto K_U = K_W = vazio, e K não é uma cobertura em G.
Uma mudança no enunciado que eu acredito que "corrigiria" isso é redefinir K_U para:
K_U = vértices de U que não são pontas de caminhos que comecem em U'. (ou os vértices cobertos pelo emparelhamento cuja outra ponta não esteja em K_W)
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!
Ou seja, com K_U = (U \ L) e K_W=(W intersecção L), dá pra provar o negócio!