Кнезерів граф ${\displaystyle KG_{n,k}}$ — це неорієнтований граф, що описує відношення неперетинності ${\displaystyle k}$-елементних підмножин ${\displaystyle n}$-елементної множини між собою.

Нехай ${\displaystyle R_{n}=\{1,2,\cdots ,n\}}$. Тоді кнезерів граф ${\displaystyle KG_{n,k}=(V,E)}$ визначається як пара множин вершин ${\displaystyle V=\{S\mid S\subset R_{n},|S|=k\}}$ і ребер ${\displaystyle E=\{(A,B)\mid A\in V,B\in V,A\cap B=\varnothing \}}$

• При ${\displaystyle k>{\frac {n}{2}}}$ кнезерів граф є порожнім графом (без ребер).

• При ${\displaystyle k={\frac {n}{2}}}$ кнезерів граф являє собою парування. Звичайно, розглядається лише випадок ${\displaystyle n\equiv 0{\pmod {2}}}$

• При ${\displaystyle k=1}$ кнезерів граф є повним графом.

• Граф ${\displaystyle KG_{5,2}}$ є графом Петерсена.

• Основний інтерес становлять кнезерові графи зі значеннями параметра ${\displaystyle k}$ в проміжку ${\displaystyle [2;{\frac {n}{2}})}$.

Кнезерів граф, крім усього іншого, можна використати для ілюстрації часткового випадку непрактичності тривіальних оцінок хроматичного числа графу через клікове число і число незалежності.

Числом незалежності ${\displaystyle \alpha (G)}$ називається розмір максимально незалежної множини вершин у графі ${\displaystyle G}$. Визначення розмальовки означає, що ${\displaystyle \alpha (G)}$ визначає максимальну кількість вершин, яку можна пофарбувати в один колір. Виходячи з деякої модифікації принципу Діріхле, хроматичне число графу можна оцінити як ${\displaystyle \chi (G)\geq {\frac {|V|}{\alpha (G)}}}$

Аналогічно визначається клікове число ${\displaystyle \omega (G)}$ як розмір максимальної кліки. Це число дає оцінку ${\displaystyle \chi (G)\geq \omega (G)}$

Як правило, перша оцінка краща від другої — а саме, для випадкового графу ${\displaystyle G}$ на ${\displaystyle n}$ вершинах ймовірність того, що ${\displaystyle \alpha (G)<2\log _{2}{n}}$ прямує до одиниці зі зростанням ${\displaystyle n}$. З того, що кожній із клік графу ${\displaystyle G}$ можна зіставити незалежну множину графу ${\displaystyle \not G}$, можна зробити висновок, що те саме виконується для ${\displaystyle \omega (G)}$.

Однак кнезерів граф дає наочну ілюстрацію цілого класу графів, що дискредитують викладені вище оцінки (в загальному випадку, а не для випадкових графів).

Не обмежуючи загальності, припустимо, що ${\displaystyle \{1,\dots ,k\}}$ входить у кліку як вершина. Тоді, з визначення кліки, жодна інша вершина не повинна містити у своїй підмножині жодного елемента з ${\displaystyle \{1,\dots ,k\}}$. При подальшому аналогічному аналізі це очевидним чином дає ${\displaystyle \omega (KG_{n,k})=\left\lfloor {\frac {n}{k}}\right\rfloor }$

З комбінаторних міркувань очевидно, що ${\displaystyle \alpha (KG_{n,k})\geq {\binom {n-1}{k-1}}}$. Для побудови незалежної множини такого розміру достатньо зафіксувати одну вершину і перебрати всі ${\displaystyle k}$-елементні підмножини, що містять її. За визначенням, між будь-якою парою таких множин не буде ребра.

Ердеш, Ко^[en] і Радо^[en] 1961 року опублікували доведення теореми, що стверджує рівність у викладеній вище оцінці. За словами математиків, вони знайшли доведення ще за кілька десятиліть до цього, але тоді не було сенсу його публікувати, тому що теорема нікого не цікавила. До речі, граф Кнезера в той час ще не був відомий, так що Ердеш, Ко і Радо доводили теорему в елементарному формулюванні максимальної кількості ${\displaystyle k}$-елементних підмножин ${\displaystyle n}$-елементної множини, що попарно перетинаються.

Користуючись тривіальною оцінкою, з даного значення числа незалежності можна отримати лише ${\displaystyle \chi (KG_{n,k})\geq {\frac {\binom {n}{k}}{\binom {n-1}{k-1}}}={\frac {n}{k}}}$, тобто ${\displaystyle \chi (KG_{n,k})\geq \left\lceil {\frac {n}{k}}\right\rceil }$. Ця оцінка майже не відрізняється від оцінки через клікове число.

Сформульована 1955 року Мартіном Кнезером^[en] і доведена 1977 року Ласло Ловасом теорема стверджує, що ${\displaystyle \chi (KG_{n,k})=n-2k+2}$

Для будь-якого ${\displaystyle j=1,2,\ldots ,n-2k+1}$ пофарбуємо в ${\displaystyle j}$-й колір кожну підмножину, мінімальним елементом якої є число ${\displaystyle j}$. Пофарбуємо в колір ${\displaystyle n-2k+2}$ кожну з підмножин, що містяться у множині ${\displaystyle \{n-2k+2,n-2k+3,\ldots ,n\}}$. Оскільки в зазначеній множині ${\displaystyle 2k-1}$ елемент, то будь-які дві її ${\displaystyle k}$-елементних підмножини перетинаються, тобто між відповідними вершинами немає ребра. Отже, побудована розмальовка правильна.

• Розфарбовування графів
• Хроматичне число
• Кліка (теорія графів)
• Незалежна множина (теорія графів)

• Науково-популярний фізико-математичний журнал «Квант», 2011 рік, «Гіпотеза Кнезера і топологічний метод у комбінаториці» (А. Райгородський)