|
Пусть [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 ~~~ \textbf{(1)}[/math]
Пусть в графе [math]G' \setminus S[/math] всего [math]t[/math] компонент связности, [math]n[/math] из которых нечётны. Тогда пусть [math]U_1, \cdots, U_n[/math] — нечётные компоненты связности [math]G' \setminus S[/math], тогда [math]|odd(G' \setminus S)| = n[/math], а [math]U_{n+1}, \cdots, U_t[/math] — его чётные компоненты связности. Для каждого [math]i \in [1 \cdots t][/math] определим три величины:
[math]A_i[/math] — рёбра из [math]E(G')[/math], соединяющие [math]U_i[/math] с [math]S[/math], [math]\alpha_i[/math] — их количество, то есть [math]\alpha_i = |A_i|[/math]
[math]B_i[/math] — рёбра из [math]F[/math], соединяющие [math]U_i[/math] с [math]S[/math], [math]\beta_i[/math] — их количество, то есть [math]\beta_i = |B_i|[/math]
[math]C_i[/math] — рёбра из [math]F[/math], соединяющие [math]U_i[/math] с остальными компонентами связности графа [math]G' \setminus S[/math], [math]\gamma_i[/math] — их количество, то есть [math]\gamma_i = |C_i|[/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]\sum\limits_{i=1}^n \alpha_i + \sum\limits_{i=1}^n \beta_i + \sum\limits_{i=1}^n \gamma_i \geqslant kn ~~~ \textbf{(2)}[/math]
Заметим, что все множества рёбер [math]A_i \subset E(G')[/math] и [math]B_j \subset F[/math] не пересекаются(так как [math]E(G') = E(G) \setminus F[/math]) и ведут во множество [math]S[/math]. Поэтому сумма [math]\sum\limits_{i=1}^t |A_i| + \sum\limits_{i=1}^t |B_i| = \sum\limits_{i=1}^t \alpha_i + \sum\limits_{i=1}^t \beta_i[/math] не превосходит суммарную степень вершин в [math]S[/math]. Во множестве [math]S[/math] находится всего [math]|S|[/math] вершин, степень каждой не превосходит [math]k[/math]. Поэтому суммарная степень вершин в [math]S[/math] не превосходит [math]k|S|[/math]. Отсюда получаем неравенство:
[math]\sum\limits_{i=1}^t \alpha_i + \sum\limits_{i=1}^t \beta_i \leqslant k|S| ~~~ \textbf{(3.1)}[/math]
Заметим, что множества рёбер [math]B_i[/math] и [math]C_j[/math], не пересекаются, так как [math]B_i[/math] ведут из [math]U_i[/math] в [math]S[/math], а [math]C_j[/math] ведут из [math]U_j[/math] в [math]U_k[/math], ([math]k \neq j[/math]). Так как [math]B_i \subset F[/math] и [math]C_j \subset F[/math], то сумма [math]\sum\limits_{i=1}^t |B_i| + \sum\limits_{i=1}^t |C_i| = \sum\limits_{i=1}^t \beta_i + \sum\limits_{i=1}^t \gamma_i[/math] не превосходит мощности [math]F[/math], откуда имеем:
[math]2 \sum\limits_{i=1}^t \beta_i + \sum\limits_{i=1}^t \gamma_i \leqslant 2|F| \leqslant 2k - 2 ~~~ \textbf{(3.1)}[/math] (так как [math]|F| \leqslant k - 1[/math])
Сложив [math]\textbf{(3.1)}[/math] и [math]\textbf{(3.2)}[/math], получаем
[math]\sum\limits_{i=1}^t \alpha_i + 3\sum\limits_{i=1}^t \beta_i + \sum\limits_{i=1}^t \gamma_i \leqslant k(|S| + 2) - 2 ~~~ \textbf{(3)}[/math]
Так как [math]\sum\limits_{i=1}^n \alpha_i + \sum\limits_{i=1}^n \beta_i + \sum\limits_{i=1}^n \gamma_i \leqslant \sum\limits_{i=1}^t \alpha_i + \sum\limits_{i=1}^t \beta_i + \sum\limits_{i=1}^t \gamma_i \leqslant \sum\limits_{i=1}^t \alpha_i + 3\sum\limits_{i=1}^t \beta_i + \sum\limits_{i=1}^t \gamma_i[/math] из неравенств [math]\textbf{(2)}[/math] и [math]\textbf{(3)}[/math] получаем [math]kn \leqslant k(|S| + 2) - 2[/math]
Тогда [math]k(n - |S| - 2) \leqslant -2[/math], следовательно, [math]k(n - |S| - 2) \leqslant 0[/math]
[math]k \gt 0[/math], следовательно [math]n - |S| - 2 \leqslant 0[/math]
и, следовательно, [math]odd(G' \setminus S) = n \lt |S| + 2[/math], что противоречит [math]\textbf{(1)}[/math]. Таким образом, множество Татта найти нельзя, значит, в [math]G'[/math] существует совершенное паросочетание. | 