У теорії графівграф Клебша — один з двох взаємодоповняльних графів, що мають 16 вершин. Один з них має 40 ребер і є 5-регулярним графом, інший має 80 ребер і є 10-регулярним графом. 80-реберний варіант — це половинний граф куба[en] 5-го порядку. 1968 року Зайдель[de][2] назвав його графом Клебша, зважаючи на його зв'язок із конфігурацією прямих поверхні четвертого порядку, яку відкрив 1868 року німецький математик Альфред Клебш. 40-реберний варіант — це складений граф куба[en] 5 порядку. Він відомий також під назвою граф Грінвуда — Глізона після роботи Грінвуда і Глізона[3], в якій вони використали цей граф для обчислення числа РамсеяR(3,3,3) = 17[3][4][5].
Складаний граф куба[en] 5-го порядку (5-регулярний граф Клебша) можна побудувати, додавши ребра між протилежними вершинами графа 4-вимірного гіперкуба (В n-вимірному гіперкубі пара вершин протилежна, якщо найкоротша відстань між ними містить n ребер). Його можна побудувати також із графа 5-вимірного гіперкуба стягуванням кожної пари протилежних вершин.
Ще одна побудова, що дає той самий граф, полягає у створенні вершини для кожного елемента скінченного поля GF (16) і з'єднанні двох вершин ребром, якщо різниця відповідних елементів поля є кубом[6].
Половинний граф куба[en] 5-го порядку (10-регулярний граф Клебша) — це доповнення 5-регулярного графа. Його можна також побудувати з вершин 5-вимірного гіперкуба, з'єднавши пари вершин, між якими відстань Геммінга дорівнює рівно два. Ця побудова утворює дві підмножини по 16 вершин у кожній, не пов'язаних між собою. Обидва отриманих графи ізоморфні 10-регулярному графу Клебша.
Властивості
5-регулярний граф Клебша є сильно регулярним графом 5-го степеня з параметрами [7]. Його доповнення, 10-регулярний граф Клебша, теж сильно регулярний[1][5].
Ребра повного графаK16 можна розділити на три незв'язних копії 5-регулярного графа Клебша. Оскільки граф Клебша не містить трикутників, це показує, що існує триколірне розфарбування без трикутників ребер графа K16. Таким чином, число РамсеяR(3,3,3), що описує найменше число вершин у повному графі за триколірного розфарбовування без трикутників, не може бути меншим від 17. Грінвуд і Глізон використали цю побудову як частину свого доведення рівності R(3,3,3) = 17[3][8].
5-регулярний граф Клебша є графом Келлера розмірності два, і входить до сімейства графів, використовуваних для пошуку покриття евклідових просторів великої розмірності гіперкубами, що не мають спільних граней.
Алгебричні властивості
Характеристичний многочлен 5-регулярного графа Клебша — це . Отже, граф Клебша є цілим графом — його спектр складається тільки з цілих чисел[5]. Граф Клебша — єдиний граф із таким характеристичним многочленом.