Изменения
→Теорема о мощности MVC и MM
Очевидно, что ребер из <tex>L^+</tex> в <tex>R^-</tex> и из из <tex>R^+</tex> в <tex>L^-</tex> быть не может.
Ребер из из <tex>R^-</tex> в <tex>L^+</tex> быть не может, т.к. если такое ребро <tex>uv</tex> существует, то оно – ребро паросочетания. Тогда вершина <tex>v</tex> насыщена паросочетанием. Но т.к. <tex>v \in L^+</tex>, то в нее можно дойти из какой-то насыщенной ненасыщенной вершины правой левой доли. Значит, существует ребро <tex>wv, w \in R^+</tex>. Но тогда <tex>v</tex> инцидентны два ребра из паросочетания. Противоречие.
Заметим, что минимальным вершинным покрытием <tex>G</tex> является либо <tex>L</tex>, либо <tex>R</tex>, либо <tex>L^- \cup R^+</tex>.
