Изменения

что каждая вершина <tex>G</tex> инцидентна<br/> не более чем одному ребру из <tex>M</tex>.

}}

{{Определение|definition=

Максимальным паросочетанием <tex>MM</tex> <tex>(maximum</tex> <tex>matching)</tex> в графе <tex>G</tex> называется паросочетание

максимальной мощности.

}}

{{Определение|definition=

Вершинным покрытием <tex>VC</tex> <tex>(vertex</tex> <tex>covering)</tex> графа <tex>G</tex> называется такое подмножество множества вершин графа <tex>V</tex>, что каждому ребру <tex>G</tex><br/> инцидентна хотя бы одна вершина из <tex>VC</tex>.

Минимальным вершинным покрытием <tex>MVС</tex> <tex>(minimum</tex> <tex>vertex</tex> <tex>covering)</tex> графа <tex>G</tex> называется вершинное покрытие минимальной мощности.

}}

==Связь MM и MVC в двудольном графе==

{{Теорема|statement=