|
Заметим, что без S граф G разваливается на чётные и нечётные компоненты связности. Нечётные компоненты нельзя покрыть паросочетанием (потому что нечётное число нельзя разбить на пары), а совершенное паросочетание у нас всё таки есть, значит из каждой нечётной компоненты шло хотя бы одно ребро в вершины из S (это ребро мы и брали в паросочетание). Но тогда вершин в S не меньше, чем нечётных компонент связности в G-S. Т.е. $`o(G-S) ≥ |S|`$.
|
|
Заметим, что без S граф G разваливается на чётные и нечётные компоненты связности. Нечётные компоненты нельзя покрыть паросочетанием (потому что нечётное число нельзя разбить на пары), а совершенное паросочетание у нас всё таки есть, значит из каждой нечётной компоненты шло хотя бы одно ребро в вершины из S (это ребро мы и брали в паросочетание). Но тогда вершин в S не меньше, чем нечётных компонент связности в G-S. Т.е. $`o(G-S) ≥ |S|`$.
|