У теорії графів граф Гершеля — двочастковий неорієнтований граф із 11 вершинами і 18 ребрами, найменший негамільтонів поліедральний граф. Граф названо на честь британського астронома А. С. Гершеля^[en], який написав ранню роботу з приводу гри «Ікосіан» Вільяма Ровена Гамільтона — граф Гершеля дає найменший опуклий многогранник, для якого гра не має розв'язку. Однак стаття Гершеля описує розв'язок для гри «Ікосіан» тільки для тетраедра та ікосаедра, і не описує графа Гершеля^[1].

Граф Гершеля планарний — його можна намалювати на площині без перехрещення ребер. Він також 3-вершинно-зв'язний — видалення будь-яких двох вершин залишає підграф зв'язним. Тому, за теоремою Штайніца, граф Гершеля є багатогранним графом — існує опуклий многогранник (еннеаедр), для якого він є скелетом^[2]. Граф Гершеля є також двочастковим — його вершини можна розбити на дві підмножини з п'яти і шести вершин так, що кожне ребро матиме кінцеві вершини в обох множинах (червоні та сині підмножини на малюнку).

Як і будь-який інший двочасковий граф, граф Гершеля є досконалим — хроматичне число будь-якого породженого підграфа дорівнює розміру найбільшої кліки цього підграфа. Граф має хроматичний індекс 4, обхват 4, радіус 3 та діаметр 4.

Оскільки граф двочастковий і має непарне число вершин, він не містить гамільтонового циклу (циклу з ребер, який проходить через кожну вершину рівно один раз). У будь-якому двочастковому графі будь-який цикл має поперемінно проходити обидві множини вершин, тому повинен містити однакову кількість вершин обох типів і мати парну довжину. Таким чином, цикл, що проходить через кожну з одинадцяти вершин, не може існувати. Граф є мінімальним негамільтоновим багатогранним графом, хоч би як вимірювався розмір графа — за кількістю вершин, ребер чи граней^[3]. Існує інший багатограний граф з 11 вершинами, що не має гамільтонових циклів (а саме, граф Голднера — Харарі), але немає графа з меншим (або рівним) числом ребер^[2].

Усі вершини графа Гершеля, крім трьох, мають степінь три. Гіпотеза Тета^[4] стверджує, що багатогранний граф, у якому будь-яка вершина має степінь три, має бути гамільтоновим, але її спростував Татт, навівши контрприклад — значно більший граф Татта^[5]. Оновлення гіпотези Тета, гіпотеза Барнетте, що будь-який двочастковий 3-регулярний багатогранний граф є гамільтоновим, залишається відкритою^[6].

Граф Гершеля є також прикладом багатоганного графа, для якого серединний граф не можна розбити на два гамільтонових цикли, що не перетинаються по ребрах. Серединним графом графа Гершеля є 4-регулярний граф з 18 вершинами, по одній для кожного ребра графа Гершеля. Дві вершини серединного графа суміжні, якщо відповідні ребра графа Гершеля йдуть послідовно на одній із його граней^[7].

Граф Гершеля не вершинно-транзитивний і його повна група автоморфізмів ізоморфна діедральній групі 12 порядку, групі симетрій правильного шестикутника, що включає як обертання, так і відбиття. Будь-яку перестановку його вершин степеня 4 можна подати автоморфізмом графа, і існує ще нетривіальний автоморфізм, що переставляє решту вершин, не зачіпаючи вершин степеня 4.

Характеристичний многочлен графа Гершеля дорівнює ${\displaystyle -x^{3}(x^{2}-11)(x^{2}-3)(x^{2}-2)^{2}}$.

• Weisstein, Eric W. Граф Гершеля(англ.) на сайті Wolfram MathWorld.