Формула Вітні

Нехай [math]K[/math] - деякий набір [math]x[/math] фарб. Відображення [math]\varphi[/math] з безлічі вершин [math]V[/math] у [math]K[/math] , що не є розфарбуванням графа [math]G[/math] , називатимемо йогоневласним розфарбуванням. Тобто, для того щоб відображення було невласним розфарбуванням, колір кінців хоча б одного ребра повинен збігатися.Власнимрозфарбуванням називатимемо розмальовку графа. Усього власних і невласних [math]x[/math]-розмальовок графа [math]G[/math] - [math]x^n[/math].

Візьмемо деяке власне чи невласне забарвлення графа [math]G[/math] . Видалимо з графа кожне ребро, кінці якого розфарбовані у різний колір. Отримаємо кістяковий подграф [math]H[/math] , в якому кожне ребро з'єднує вершини однакового кольору. Вихідне власне або невласне забарвлення називатимемо строго невласним розфарбуванням остовного підграфа [math]H[/math] . Кожній компоненті зв'язності графа [math]H[/math] відповідає один колір — колір її вершин. Якщо кістяковий подграф [math]H[/math] має [math]i[/math] компонент зв'язності, то існує [math]x^i[/math] різних строго невласних розмальовок, що відповідають кістяковому подграфу [math]H[/math ]. Кожна власна або невласна розмальовка графа [math]G[/math] є строго невласним розфарбуванням його остовного підграфа. Власним розмальовкам графа [math]G[/math] відповідає нульовий кістяковий подграф.

Нехай [math]N(i, j)[/math] — число кістяних підграфів графа [math]G[/math] , що мають [math]i[/math] компонент зв'язності та [math]j[/math] ребер.

Із загального числа [math]x^n[/math] власних таневласних розмальовок віднімемо число суворо невласних розмальовок кістяків, що мають рівно одне ребро. Якщо ми віднімемо суму [math] \sum \limits_[/math] , то ми віднімемо крім зазначеного числа ще й деяку надмірну величину. Справді, розглянемо два різних ребра графа [math] G [/ math]: [math] e_1 [/ math] і [math] e_2 [/ math]. До строго невласних розмальовок кістяного подграфа, що містить тільки ребро [math] e_1 [/ math] потраплять забарвлення, у яких кінці [math] e_2 [/ math] мають однаковий колір. Те саме вірно і для остовного подграфа, що містить тільки ребро [math] e_2 [/ math]. Виходить, що ми двічі віднімемо число строго невласних розмальовок для остовного подграфа [math]G[/math], що містить два ребра: [math] e_1 [/math] і [math] e_2 [/math]. Аналогічно буде віднято число строго невласних розмальовок остовних підграф з великим числом ребер.

Спробуємо компенсувати дворазове віднімання додаванням [math]\sum \limits_[/math] , проте при цьому додасться надлишок строго невласних розмальовок для остовних підграф з трьома, чотирма і більше ребрами. Подібну конструкцію можна розрахувати за формулою включення-виключення.