Полиэдральный граф
Полиэдральный граф — неориентированный граф, образованный из вершин и рёбер выпуклого многогранника, или, в контексте теории графов — вершинно 3-связный планарный граф.
Диаграмма Шлегеля выпуклого многогранника представляет его вершины и рёбра как точки и отрезки на евклидовой плоскости, образуя разбиение внешнего выпуклого многоугольника на более мелкие выпуклые многоугольники. Диаграмма не имеет самопересечений, так что любой полиэдральный граф является также планарным. Кроме того, по теореме Балинского, этот граф является вершинно 3-связным.
Согласно теореме Штейница этих двух свойств достаточно, чтобы полностью описать полиэдральные графы — это в точности вершинно 3-связные планарные графы. Таким образом, если граф и планарен, и вершинно 3-связен, существует многогранник, вершины и рёбра которого образуют изоморфный исходному граф[1][2]. Если задан такой граф, представление его в виде разбиения выпуклого многоугольника на меньшие выпуклые многоугольники может быть найдено с помощью вложение Татта[3].
Тэйт высказал гипотезу, что любой кубический полиэдральный граф (то есть полиэдральный граф, в котором каждая вершина инцидентна в точности трём рёбрам) имеет гамильтонов цикл, но эта гипотеза была опровергнута Уильямом Таттом, построившим контрпример — полиэдральный негамильтонов граф (граф Татта). Если ослабить условие, что граф должен быть кубическим, появится много других меньших по размерам негамильтоновых полиэдральных графов, один из них, имеющий 11 вершин и 18 рёбер — граф Хершеля[4], существует также негамильтонов полиэдральный граф с 11 вершинами, в котором все грани треугольны — граф Голднера — Харари[5].
Строго говоря, существует константа (показатель короткости[уточнить]) и бесконечное семейство полиэдральных графов, таких что длина самого длинного простого пути графа с вершинами в семействе равна [6][7].
В 1996 году определено число полиэдральных графов, имеющих до 26 рёбер[8], в частности, число таких графов с 6, 7, …, 21 рёбрами равно: