В теорії графів теорема Візінга названа на честь Вадіма Візінга який оприлюднив її в 1964 стверджує що ребра кожного нео

В теорії графів, теорема Візінга (названа на честь Вадіма Візінга, який оприлюднив її в 1964) стверджує, що ребра кожного неорієнтованого графу можна пофарбувати, із використанням числа кольорів не більшого ніж найбільший степінь $Δ$ графу плюс 1.

Завжди необхідно не менше ніж $Δ$ кольорів, отже неорієнтовані графи можна розділити на два класи: «клас один», для якого достатньо $Δ$ кольорів, і «клас два», для якого необхідно $Δ + 1$ .

Приклади

коли $Δ = 1$ , граф $G$ не має двох суміжних ребер і його хроматичне число — один. Тобто всі графи з $Δ(G) = 1$ належать до першого класу.

Коли $Δ = 2$ , граф $G$ повинен бути диз'юнктним об'єднанням шляхів і циклів. Якщо всі цикли парні, тоді їх можна розфарбувати двома кольорами, чергуючи їх. Якщо ж існує хоч один непарний цикл, тоді розфарбування 2 кольорами неможливе. Тобто граф з $Δ = 2$ належить до першого класу тоді і тільки тоді, якщо двочастковий.

Мультиграфи зазвичай не коряться теоремі Візінга. Наприклад, мультиграф утворений подвоєнням кожного ребра у трикутнику має максимальну валентність вершини чотири, але його розфарбування вимагає шість кольорів.

Посилання

Доведення теореми Візінга на PlanetMath. (англ.)