Теорема Котцигса - Википедия - Kotzigs theorem

В триакис икосаэдр, многогранник, каждое ребро которого имеет конечные точки с суммарной степенью не менее 13

В теория графов и многогранная комбинаторика, области математики, Теорема Коцига утверждение, что каждый многогранный граф имеет край, две конечные точки которого имеют общее степень не более 13. Крайним случаем является триакис икосаэдр, где никакое ребро не имеет меньшей общей степени. Результат назван в честь Антон Коциг, опубликовавший его в 1955 г. в двойной форма, что каждый выпуклый многогранник имеет две смежные грани, всего не более 13 сторон.^[1] Он был назван и популяризирован на Западе в 1970-х годах. Бранко Грюнбаум.^[2][3]

В более общем смысле, каждый плоский граф минимальной степени не менее трех либо имеет ребро общей степени не более 12, либо не менее 60 ребер, которые (подобно ребрам в триакисикосаэдре) соединяют вершины степеней 3 и 10.^[4]Если все треугольные грани многогранника вершинно-непересекающиеся, существует ребро с меньшей общей степенью, не более восьми.^[5]Известны также обобщения теоремы вложения графов на поверхности с более высокими род.^[6]

Теорема не может быть обобщена на все планарные графы, как полные двудольные графы ${ displaystyle K_ {1, n-1}}$ и ${ displaystyle K_ {2, n-2}}$ имеют ребра с неограниченной суммарной степенью. Однако для плоских графов с вершинами степени ниже трех были доказаны варианты теоремы, показывающие, что существует либо ребро ограниченной полной степени, либо подграф другого особого вида.^[7]

Рекомендации