Триакисикосаэдр — многогранник, в котором каждое ребро имеет конечные точки с общей степенью не менее 13.
В теории графов и полиэдральной комбинаторике , областях математики, теорема Коцига — это утверждение, что каждый полиэдральный граф имеет ребро, две конечные точки которого имеют общую степень не более 13. Крайним случаем является триакисикосаэдр , где ни одно ребро не имеет меньшей общей степени. Результат назван в честь Антона Коцига , который опубликовал его в 1955 году в двойственной форме, что каждый выпуклый многогранник имеет две смежные грани с общей степенью не более 13 сторон. [1] Он был назван и популяризирован на Западе в 1970-х годах Бранко Грюнбаумом . [2] [3]
В более общем смысле, каждый планарный граф минимальной степени не менее трех либо имеет ребро общей степени не более 12, либо не менее 60 ребер, которые (как ребра в триакисикосаэдре) соединяют вершины степеней 3 и 10. [4]
Если все треугольные грани многогранника вершинно-непересекающиеся, то существует ребро с меньшей общей степенью, не более восьми. [5]
Обобщения теоремы также известны для вложений графов на поверхности с более высоким родом . [6]
Теорема не может быть обобщена на все планарные графы , так как полные двудольные графы и имеют ребра с неограниченной общей степенью. Однако для планарных графов с вершинами степени ниже трех были доказаны варианты теоремы, показывающие, что либо существует ребро ограниченной общей степени, либо некоторый другой специальный вид подграфа. [7]
Ссылки
^ Коциг, Антон (1955), «Вклад в теорию эйлеровых многогранников», Matematicko-Fyzikálny Časopis , 5 : 101–113, MR 0074837
^ Грюнбаум, Бранко (1975), «Многогранные графы», Исследования по теории графов, Часть II , MAA Studies in Mathematics, т. 12, стр. 201–224, MR 0406868
^ Грюнбаум, Бранко (1976), «Новые взгляды на некоторые старые вопросы комбинаторной геометрии», Colloquio Internazionale sulle Teorie Combinatorie (Рим, 1973), Tomo I , Atti dei Convegni Lincei, vol. 17, стр. 451–468, МР 0470861
