52
правки
Изменения
м
→Теорема Эдмондса
|proof=
Пусть граф <tex>G'</tex> - граф, полученный <tex>G</tex> сжатием соцветия <tex>B</tex> в псевдо-вершину <tex>B'</tex>.<br />
Заметим, что достаточно рассматривать случай, когда база соцветия является свободной вершиной (не принадлежащей паросочетанию). Действительно, в В противном случае в базе соцветия оканчивается чередующийся путь чётной длины, начинающийся в свободной вершине. Прочередовав паросочетание вдоль этого пути, мощность паросочетания не изменится, а база соцветия станет свободной вершиной.
<tex>\Rightarrow</tex>
