Формула на Уитни

Нека [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] , но това ще добави излишък от строго неправилни оцветявания за обхващащи подграфи с три, четири или повече ръба. Такава конструкция може да се изчисли с помощта на формулата за включване-изключване.