Теорема о существовании совершенного паросочетания в графе, полученном из регулярного удалением ребёр

Теорема (J. Plesnik, 1972):

Пусть [math]G[/math] — [math]k[/math]-регулярный граф, с чётным числом вершин, причём [math]\lambda(G) \geqslant k - 1[/math], а граф [math]G'[/math] получен из [math]G[/math] удалением не более [math]k - 1[/math] рёбер. Тогда в графе [math]G'[/math] есть совершенное паросочетание.

Доказательство:

[math]\triangleright[/math]

Пусть [math]G' = G \setminus F[/math], где [math]F \subset E(G)[/math], тогда [math]|F| \leqslant k - 1[/math] Предположим, что в [math]G'[/math] нет совершенного паросочетания, тогда выберем множество Татта [math]S \subset V(G')[/math], тогда [math]odd(G' \subset S) \gt |S|[/math] Так как [math]|V(G)|[/math] чётно, то и [math]odd(G' \setminus S) + |S|[/math] тоже чётно. Из этого следует, что [math]odd(G' \setminus S) \equiv |S| \pmod 2 [/math]. Из этого факта и того, что [math]odd(G' \setminus S) \gt |S|[/math] следует, что [math]odd(G' \setminus S) \geqslant |S| + 2[/math] Пусть [math]U_1, \cdot, U_n[/math] — нечётные компоненты связности [math]G' \setminus S[/math], тогда [math]|odd(G' \setminus S)| = n[/math], а [math]U_{n+1}, \cdot, U_t[/math] — его чётные компоненты связности. Для каждого [math]i \in [1 \cdots t][/math] определим три величины: [math]\alpha_i[/math] — количество рёбер из [math]E(G')[/math], соединяющих [math]U_i[/math] с [math]S[/math], [math]\beta_i[/math] — количество рёбер из [math]F[/math], соединяющих [math]U_i[/math] с [math]S[/math], [math]\gamma_i[/math] — количество рёбер из [math]E(G')[/math], соединяющих [math]U_i[/math] с остальными компонентами связности графа [math]G' \setminus S[/math], тогда [math]m_i := \alpha_i + \beta_i + \gamma_i[/math]. Тогда [math]m_i[/math] — это количество рёбер графа [math]G[/math], соединяющих [math]U_i[/math] с [math]V(G) \setminus U_i[/math]. По лемме о сравнимости по модулю 2 для нечётных компонент связности [math]G' \setminus S[/math] (то есть [math]i \in [1 \cdots n][/math]) [math]m_i \equiv k \pmod 2[/math]. [math]m_i \geqslant \lambda(G) \geqslant k - 1[/math]. Из этого факта и того, что [math]m_i \equiv k \pmod 2[/math] следует, что [math]m_i \geqslant k[/math]. Отсюда получаем неравенство

[math]\triangleleft[/math]