Досконалепаросполучення в кубічному графі
[math]m = (\sum\limits_ d_G(v)) - 2e(G(U))[/math] , де [math]e(G(U))[/math] — кількість ребер, що з'єднують вершину з [math]U[/math] з іншою вершиною з [math]U[/math].
тоді [math]m = kU - 2e(G(U))[/math].
[math]2e(G(U))[/math] парно, тому [math]m \equiv kU \pmod 2[/math] . Оскільки [math] U[/math] непарно, [math]m \equiv k \pmod 2[/math] .
Припустимо, що досконалого паросполучення в [math]G[/math] немає, тоді можна вибрати безліч Татта [math]S\subset V(G)[/math].
Нехай [math] U_1, \ldots, U_n[/math] - всі непарні компоненти зв'язності графа [math]G \setminus S[/math]. [math]m_i[/math] - кількість ребрів [math]G[/math] , що зв'язують вершини [math]U_i[/math] з вершинами [math]S[/math] .
По попередній лемі, всі [math] m_i [/ math] непарні. Оскільки не більше ніж два ребра графа [math]G[/math] — мости, то не більше ніж два числа з [math]m_1, \ldots, m_n[/math] рівні [math]1[/math] , інші числа не менше [math] 3 [/ math].
Оскільки [math]S[/math] - безліч Татта, то [math]odd(Gsetminus S) \gt S[/math]. Оскільки кількість вершин кубічного графа [math]G[/math] парно, ми маємо [math]S \neq \emptyset, odd(G \setminus S) \equiv S \pmod 2[/math] , отже, [math] n = odd (G \ setminus S) \ geqslant S + 2 [/ math] . Тоді
[math]\sum\limits_ d_G(v) \geqslant \sum\limits_^n m_i \geqslant 3n - 4 \geqslant 3(S + 2) - 4 = 3S + 2 \gt 3S = \sum\limits_ d_G(v)[/math] , що, очевидно, неможливо.
Знайдено протиріччя, отже, безліч Татта вибрати неможливо, отже, [math]G[/math] є досконале паросполучення.
Зауважимо, що твердження теореми не може бути посилено до більшої кількості мостів, тому що для випадку з трьома мостами існуєконтрприклад.
Візьмемо ребро [math] p = (c, d) [/ math]. Нехай вершини [math]a[/math] і [math]b[/math] суміжні з вершиною [math]c[/math], а вершини [math]e[/math] і [math]f[/math] суміжні з вершиною [math]d[/math] (малюнок [math]1(a)[/math]).
Як мінімум одне з двох скорочень графа [math]G[/math] , що складається з видалення вершин [math]c, d[/math] і переєднання вершин [math]a, b, e, f[/math] ребрами [math] ](a, e), (b, f)[/math] або [math](a, f), (b, e)[/math] (малюнок [math]1 (b), (c)[/ math], малюнок [math]2[/math]) збереже двозв'язність графа.
Позначимо компоненти графа [math]G(V - \)[/math] як [math]A, B, E, F[/math] , які містять вершини [math]a, b, e, f[/math] відповідно . Так як [math]G[/math] не має мостів (відповідно [math]p[/math] не є мостом) має існувати ребро, що з'єднує одну з компонентів [math]A[/math] або [math]B[/ math] , з однією з компонентів [math]E[/math] або [math]F[/math] . Без втрати спільності припустимо, що [math]A[/math] з'єднане з [math]E[/math]. Зауважимо, що ребра [math](b, c), (d, f)[/math] так само не є мостами, отже можливі три випадки (з урахуванням ізоморфізму) (рисунок [math]3[/math] ):
- компонента [math]B[/math] з'єднана з [math]F[/math] ,
- компонента [math]B[/math] з'єднана з [math]E[/math] і компонента [math]E[/math] з'єднана з [math]F[/math] ,
- компонента [math]A[/math] з'єднана з [math]B[/math] і компонента [math]E[/math] з'єднана з [math]F[/math] .
У всіх трьох випадках якщо [math]G(V - \)[/math] розширити ребрами [math](a, f), (b, e)[/math] (отримаємо граф [math]G'[/math] ), додані ребра будуть лежати на деякому циклі [math]G'[/math] (малюнок [math]4[/math] ). Також для будь-якої пари вершин [math]u, v[/math] [math]\in[/math][math]\[/math] існує цикл [math]G'[/math] , що містить дані вершини. Щоб довести, що [math]G'[/math] двозв'язковий, потрібно показати, що кожне ребро [math]r[/math] з [math]G'[/math] лежить на деякому циклі [math]G'[ / Math] . Нехай цикл [math]C[/math] в [math]G[/math] містить [math]r[/math] (такий цикл існує, оскільки [math]G[/math] двозв'язний). Якщо [math]C[/math] не проходить через вершини [math]c, d[/math] тоді [math]C[/math] так само є циклом [math]G'[/math] , інакше побудуємо цикл [math]C'[/math] графа [math]G'[/math] з [math]C[/math] наступним чином:
- якщо шлях [math] x - c - d - y [/math] [math]\in[/math] [math] C [/math] , [math] x [/math] ] [math] \ [/math] , [math] y [/math] [math]\in[/math] [math] \ [/math] , видалимо цей шлях і додамо будь-який інший з [math] x [/ math] в [math] y [/math] у [math] G' [/math] , що не містить [math]r[/math] (такий шлях завжди існує, тому що [math] x [/math] і [ math] y [/math] належать деякому циклу в [math] G' [/math] ),
- якщо шлях [math] a - c - b [/math] [math]\in[/math] [math] C [/math] , видалимо цей шлях і додамо будь-який інший з [math] a [/math] в [ math] b [/math] в [math] G' [/math] , що не містить [math]r[/math] ,
- якщо шлях [math] e - d - f [/math] [math]\in[/math] [math] C [/math] , видалимо цей шлях і додамо будь-який інший з [math] e [/math] в [ math] f [/math] у [math] G' [/math] , що не містить [math]r[/math] .