Граф Хершеля

Граф Хершеля планарен — его можно нарисовать на плоскости без пересечения рёбер. Он также вершинно 3-связен — удаление любых двух вершин оставляет подграф связным. Поэтому, по теореме Штайница граф Голднера — Харари является полиэдральным графом — существует выпуклый многогранник (эннеаэдр), имеющий граф Хершеля в качестве своего скелета[2]. Граф Хершеля является также двудольным — его вершины можно разбить на два подмножества из пяти и шести вершин так, что каждое ребро имеет конечные вершины в обоих множествах (красные и синие подмножества на рисунке).

Как и любой другой двудольный граф, граф Хершеля является совершенным — хроматическое число любого порождённого подграфа равно размеру наибольшей клики этого подграфа. Граф имеет хроматический индекс 4, обхват 4, радиус 3 и диаметр 4.

Поскольку граф является двудольным и имеет нечётное число вершин, он не содержит гамильтонов цикл (цикл из рёбер, который проходит через каждую вершину в точности один раз). В любом двудольном графе любой цикл должен попеременно проходить оба множества вершин, а потому, должен содержать равное число вершин обоих типов и иметь чётную длину. Таким образом, цикл, проходящий через каждую из одиннадцати вершин, существовать не может. Граф является минимальным негамильтоновым полиэдральным графом, как бы ни измерялся размер графа — по числу вершин, рёбер или граней[3]. Существует другой полиэдральный граф с 11 вершинами, не имеющий гамильтоновых циклов (а именно, граф Голднера — Харари[4]), но нет графа с меньшим (либо равным) числом рёбер[2].

Все вершины графа Хершеля, за исключением трёх, имеют степень три. Гипотеза Тейта[5] утверждает, что полиэдральный граф, в котором любая вершина имеет степень три должен быть гамильтоновым, но она опровергнута контрпримером, который привёл Татт, много большим графом Татта[6]. Обновление гипотезы Татта, гипотеза Барнетте, что любой двудольный 3-регулярный полиэдральный граф является гамильтоновым, остаётся открытой[7].

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

Граф Хершеля не вершинно-транзитивен и его полная группа автоморфизмов изоморфна диэдрической группе 12 порядка, группе симметрий правильного шестиугольника, включающей как вращения, так и отражения. Любую перестановку его вершин четвёртой степени можно представить автоморфизмом графа, и существует ещё нетривиальный автоморфизм, переставляющий оставшиеся вершины, не затрагивая вершины четвёртой степени.

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

• Weisstein, Eric W. Herschel Graph (англ.) на сайте Wolfram MathWorld.