Перфектно съвпадение в кубична графика
[math] m = (\ sum \ limit_ d_G (v)) - 2e (G (U)) [/ math], където [math] e (G (U)) [/ math] е броят на ръбовете, свързващи a връх от [math] U [/ math] с различен връх от [math] U [/ math] .
тогава [математика] m = k | U | - 2e (G (U)) [/ математика] .
[math] 2e (G (U)) [/ math] е четно, следователно [math] m \ equiv k | U | \ pmod 2 [/ math]. Тъй като [math] | U | [/ math] е нечетно, [math] m \ equiv k \ pmod 2 [/ math] .
Да предположим, че няма перфектно съвпадение в [math] G [/ math], тогава можем да изберем Tutt set [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] е набор на Tutt, тогава [math] нечетен (G \ setminus S) \ gt | S | [/ math]. Тъй като броят на върховете на кубичната графика [math] G [/ math] е четен, имаме [math] S \ neq \ emptyset, nepar (G \ setminus S) \ equiv S \ pmod 2 [/ math], следователно, [математика] n = нечетно (G \ setminus S) \ geqslant | S | + 2 [/ математика]. Тогава
[математика] \ сума \ граници_ d_G (v) \ geqslant \ сума \ граници_^ n m_i \ geqslant 3n - 4 \ geqslant 3 (| S | + 2) - 4 = 3 | S | + 2 \ gt 3 | S | = \ sum \ limit_ 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]) ще поддържа графиката двойно свързана.