Описание ребер в плоских нормальных картах без смежных 3-граней
Ключевые слова:
плоский граф, плоская карта, структурные свойства, 3-многогранник, весАннотация
Вес $w(e)$ ребра $e$ в плоской нормальной карте (NPM) - это сумма степеней его концевых вершин. Ребро $e=uv$ является $(i,j)$-ребром, если $d(u)\le i$ и $d(v)\le j$. В 1940 г. Лебег доказал, что в каждой NPM имеется $(3,11)$-ребро, или $(4,7)$-ребро, или $(5,6)$-ребро, где 7 и 6 неулучшаемы. В 1955 г. Коциг доказал, что в каждом 3-многограннике найдется ребро $e$ с $w(e)\le13$, оцентка точна. Бородин (1987), отвечая на вопрос Эрдеша, доказал, что в каждой NPM найдется такое ребро. Более того, Бородин (1991) уточнил это, доказав, что существует или $(3,10)$-ребро, или $(4,7)$-ребро, или $(5,6)$-ребро.
Для NPM получены некоторые верхние границы минимального веса всех ее ребер, обозначаемого $w$, инцидентных 3-грани --- $w^*$, и инцидентных двум 3-граням --- $w^{**}$. В частности, Бородин (1996) доказал, что если $w^{**}=\infty$ (что имеет место, если в NPM нет ребер, инцидентных двум 3-граням), то или $w^*\le9$, или $w\le8$, причем обе оценки точны.
Целью заметки является уточнение этого результата, а именно доказательство факта, что $w^{**}=\infty$ подразумевает наличие либо $(3,6)$- или $(4,4)$-ребра, инцидентного 3-грани, либо наличие $(3,5)$-ребра, причем это описание точно.
