matmessМатематические заметки СВФУMathematical notes of NEFU2411-93262587-876XСеверо-Восточный федеральный университет имени М.К. Аммосова10.25587/2411-9326-2025-2-50-55matmess-77Research ArticleМАТЕМАТИКАDescribing edges incident with minor faces in 3-polytopes without adjacent 3-facesDescribing edges incident with minor faces in 3-polytopes without adjacent 3-facesBorodinO. V.BorodinO. V.

Oleg V. Borodin

4 Koptyug Avenue, 630090 Novosibirsk

Oleg V. Borodin

4 Koptyug Avenue, 630090 Novosibirsk

brdnoleg@math.nsc.ruIvanovaA. O.IvanovaA. O.

Anna O. Ivanova

4 Koptyug Avenue, 630090 Novosibirsk

Anna O. Ivanova

48 Kulakovskogo Street, Yakutsk 677013

shmgnanna@mail.ruSobolev Institute of MathematicsРоссияSobolev Institute of MathematicsRussian Federationmmosov North-Eastern Federal UniversityРоссияAmmosov North-Eastern Federal UniversityRussian Federation2025300620253225055Copyright © Borodin O.V., Ivanova A.O., 20252025Borodin O.V., Ivanova A.O.Borodin O.V., Ivanova A.O.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://matmess.elpub.ru/jour/article/view/77

The weight w(e) of an edge e in a 3-polytope is the degree-sum of its endvertices. An edge e = uv is an (i, j)-edge if d(u) ≤ i and d(v) ≤ j. In 1940 Lebesgue proved that every 3-polytope has a (3, 11)-edge, or (4, 7)-edge, or (5, 6)-edge, where 7 and 6 are best possible. In 1955, Kotzig proved that every 3-polytope has an edge e with w(e) ≤ 13, which bound is sharp. Borodin (1987), answering Erd˝os’ question of 1976, proved that every plane graph without vertices of degree less than 3 has such an edge. Moreover, Borodin (1991) refined this by proving that there is either a (3, 10)-edge, or (4, 7)-edge, or (5, 6)-edge.

Given a 3-polytope, the minimum weight of all its edges is denoted by w, of those incident with just one 3-face and called semi-weak is w∗, and those incident with two 3-faces and called weak, is w∗∗. Borodin (1996) proved that if w∗∗ = ∞, that is there are no weak edges, then either w∗ ≤ 9 or w ≤ 8, where both bounds are sharp.

Recently, we refined this fact by proving that w∗∗ = ∞ implies either a semi-weak (3, 6)-edge, or semi-weak (4, 4)-edge, or else a strong (3, 5)-edge, which description is tight. (Note that if (3, 5)-edges are allowed, then there may be no 3-faces, and hence semi-weak edges, at all.)

The purpose of our note is to further refine these results by proving that in fact w∗∗ = ∞ implies either a semi-weak (3, 6)-edge, or semi-weak (4, 4)-edge, or a strong (3, 5)-edge incident with a 4-face, or else a strong (3, 3)-edge incident with a 5-face, where no parameter can be improved.

The weight w(e) of an edge e in a 3-polytope is the degree-sum of its endvertices. An edge e = uv is an (i, j)-edge if d(u) ≤ i and d(v) ≤ j. In 1940 Lebesgue proved that every 3-polytope has a (3, 11)-edge, or (4, 7)-edge, or (5, 6)-edge, where 7 and 6 are best possible. In 1955, Kotzig proved that every 3-polytope has an edge e with w(e) ≤ 13, which bound is sharp. Borodin (1987), answering Erd˝os’ question of 1976, proved that every plane graph without vertices of degree less than 3 has such an edge. Moreover, Borodin (1991) refined this by proving that there is either a (3, 10)-edge, or (4, 7)-edge, or (5, 6)-edge.

Given a 3-polytope, the minimum weight of all its edges is denoted by w, of those incident with just one 3-face and called semi-weak is w∗, and those incident with two 3-faces and called weak, is w∗∗. Borodin (1996) proved that if w∗∗ = ∞, that is there are no weak edges, then either w∗ ≤ 9 or w ≤ 8, where both bounds are sharp.

Recently, we refined this fact by proving that w∗∗ = ∞ implies either a semi-weak (3, 6)-edge, or semi-weak (4, 4)-edge, or else a strong (3, 5)-edge, which description is tight. (Note that if (3, 5)-edges are allowed, then there may be no 3-faces, and hence semi-weak edges, at all.)

The purpose of our note is to further refine these results by proving that in fact w∗∗ = ∞ implies either a semi-weak (3, 6)-edge, or semi-weak (4, 4)-edge, or a strong (3, 5)-edge incident with a 4-face, or else a strong (3, 3)-edge incident with a 5-face, where no parameter can be improved.

planar graphplane mapstructure properties3-polytope3-faceedgeweightplanar graphplane mapstructure properties3-polytope3-faceedgeweightThe first author’s work was supported by the Ministry of Science and Higher Education of the Russian Federation (Project No. FWNF–2022–0017). The second author’s work was supported by the Ministry of Science and Higher Education of the Russian Federation (Grant No. FSRG–2023– 0025).The first author’s work was supported by the Ministry of Science and Higher Education of the Russian Federation (Project No. FWNF–2022–0017). The second author’s work was supported by the Ministry of Science and Higher Education of the Russian Federation (Grant No. FSRG–2023– 0025).ReferencesWernicke P., “Uber den Kartographischen Vierfarbensatz,” Math. Ann., ¨ 58, 413–426 (1904).Wernicke P., “Uber den Kartographischen Vierfarbensatz,” Math. Ann., ¨ 58, 413–426 (1904).Lebesgue H., “Quelques cons´equences simples de la formule d’Euler,” J. Math. Pures Appl., 19, 27–43 (1940).Lebesgue H., “Quelques cons´equences simples de la formule d’Euler,” J. Math. Pures Appl., 19, 27–43 (1940).Kotzig A., “Contribution to the theory of Eulerian polyhedra [in Slovak],” Mat. Cas., ˇ 5, 101– 103 (1940).Kotzig A., “Contribution to the theory of Eulerian polyhedra [in Slovak],” Mat. Cas., ˇ 5, 101– 103 (1940).Gr¨unbaum B., “New views on some old questions of combinatorial geometry,” Int. Teorie Comb., Rome, 1, 451–468 (1976).Gr¨unbaum B., “New views on some old questions of combinatorial geometry,” Int. Teorie Comb., Rome, 1, 451–468 (1976).Borodin O. V., “Coupled colorings of graphs on a plane [in Russian],” Metody Diskret. Analiza, 45, 21–27 (1987).Borodin O. V., “Coupled colorings of graphs on a plane [in Russian],” Metody Diskret. Analiza, 45, 21–27 (1987).Borodin O. V., “The structure of neighborhoods of an edge in planar graphs and the simultaneous coloring of vertices, edges and faces [in Russian],” Mat. Zametki, 53, No. 5, 35–47 (1993).Borodin O. V., “The structure of neighborhoods of an edge in planar graphs and the simultaneous coloring of vertices, edges and faces [in Russian],” Mat. Zametki, 53, No. 5, 35–47 (1993).Borodin O. V., “Joint extension of two Kotzig’s theorems on 3-polytopes,” Combinatorica, 13, No. 1, 121–125 (1992).Borodin O. V., “Joint extension of two Kotzig’s theorems on 3-polytopes,” Combinatorica, 13, No. 1, 121–125 (1992).Borodin O. V. and Ivanova A. O., “New results about the structure of plane graphs: a survey,” AIP Conf. Proc., 1907, 030051 (2017).Borodin O. V. and Ivanova A. O., “New results about the structure of plane graphs: a survey,” AIP Conf. Proc., 1907, 030051 (2017).Jendrol’ S. and Voss H.-J., “Light subgraphs of graphs embedded in the plane: a survey,” Discrete Math., 313, No. 4, 406–421 (2013).Jendrol’ S. and Voss H.-J., “Light subgraphs of graphs embedded in the plane: a survey,” Discrete Math., 313, No. 4, 406–421 (2013).Aksenov V. A., Borodin O. V., and Ivanova A. O., “An extension of Kotzig’s theorem,” Discuss. Math. Graph Theory, 36, 889–897 (2016).Aksenov V. A., Borodin O. V., and Ivanova A. O., “An extension of Kotzig’s theorem,” Discuss. Math. Graph Theory, 36, 889–897 (2016).Batueva Ts. Ch-D., Borodin O. V., Bykov M. A., Ivanova A. O., Kazak O. N., and Nikiforov D. V., “Refined weight of edges in normal plane maps,” Discrete Math., 340, No. 11, 2659–2664 (2017).Batueva Ts. Ch-D., Borodin O. V., Bykov M. A., Ivanova A. O., Kazak O. N., and Nikiforov D. V., “Refined weight of edges in normal plane maps,” Discrete Math., 340, No. 11, 2659–2664 (2017).Borodin O. V., “Joint generalization of the theorems of Lebesgue and Kotzig on the combinatorics of planar maps [in Russian],” Diskret. Mat., 3, No. 4, (1991) 24–27.Borodin O. V., “Joint generalization of the theorems of Lebesgue and Kotzig on the combinatorics of planar maps [in Russian],” Diskret. Mat., 3, No. 4, (1991) 24–27.Borodin O. V., “Structural theorem on plane graphs with application to the entire coloring,” J. Graph Theory, 23, No. 3, 233–239 (1996).Borodin O. V., “Structural theorem on plane graphs with application to the entire coloring,” J. Graph Theory, 23, No. 3, 233–239 (1996).Borodin O. V., “More about the weight of edges in planar graphs,” Tatra Mt. Math. Publ., 9, 11–14 (1996).Borodin O. V., “More about the weight of edges in planar graphs,” Tatra Mt. Math. Publ., 9, 11–14 (1996).Borodin O. V. and Ivanova A. O., “Weight of edges in normal plane maps,” Discrete Math., 339, No. 5, 1507–1511 (2016).Borodin O. V. and Ivanova A. O., “Weight of edges in normal plane maps,” Discrete Math., 339, No. 5, 1507–1511 (2016).Borodin O. V. and Ivanova A. O., “An improvement of Lebesgue’s description of edges in 3-polytopes and faces in plane quadrangulations,” Discrete Math., 342, No. 6, 1820–1827 (2019).Borodin O. V. and Ivanova A. O., “An improvement of Lebesgue’s description of edges in 3-polytopes and faces in plane quadrangulations,” Discrete Math., 342, No. 6, 1820–1827 (2019).Borodin O. V. and Ivanova A. O., “Describing edges in normal plane maps having bo adjacent 3-faces,” Sib. Elektron. Math. Rep., 21, No. 1, 495–500 (2024).Borodin O. V. and Ivanova A. O., “Describing edges in normal plane maps having bo adjacent 3-faces,” Sib. Elektron. Math. Rep., 21, No. 1, 495–500 (2024).Borodin O. V., Ivanova A. O., Kostochka A. V., and Sheikh N. N., “Minimax degrees of quasiplane graphs without 4-faces,” Sib. Elektron. Math. Rep., 4, 435–439 (2007).Borodin O. V., Ivanova A. O., Kostochka A. V., and Sheikh N. N., “Minimax degrees of quasiplane graphs without 4-faces,” Sib. Elektron. Math. Rep., 4, 435–439 (2007).Cekanov´a K., Macekov´a M., and Sotak R. ˇ , “Structure of edges in plane graphs with bounded dual edge weight,” Discrete Math., 344, No. 8, 112477 (2021).Cekanov´a K., Macekov´a M., and Sotak R. ˇ , “Structure of edges in plane graphs with bounded dual edge weight,” Discrete Math., 344, No. 8, 112477 (2021).Dvoˇr´ak Z. and Postle L., “Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8,” J. Comb. Theory Ser. B., 129, 38–54 (2018).Dvoˇr´ak Z. and Postle L., “Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8,” J. Comb. Theory Ser. B., 129, 38–54 (2018).Ferencov´a B. and Madaras T., “On the structure of polyhedral graphs with prescribed edge and dual edge weight,” Acta Univ. M. Belii Math., 12, 13–18 (2005).Ferencov´a B. and Madaras T., “On the structure of polyhedral graphs with prescribed edge and dual edge weight,” Acta Univ. M. Belii Math., 12, 13–18 (2005).Ferencov´a B. and Madaras T., “Light graph in families of polyhedral graphs with prescribed minimum degree, face size, edge and dual edge weight,” Discrete Math., 310, 1661–1675 (2010).Ferencov´a B. and Madaras T., “Light graph in families of polyhedral graphs with prescribed minimum degree, face size, edge and dual edge weight,” Discrete Math., 310, 1661–1675 (2010).Hudak P., Macekov´a M., Madaras T., and P. Siroczki, “More on the structure of plane graphs with prescribed degrees of vertices, faces, edges and dual edges,” Ars Math. Contemp., 13, No. 2, 355–366 (2017).Hudak P., Macekov´a M., Madaras T., and P. Siroczki, “More on the structure of plane graphs with prescribed degrees of vertices, faces, edges and dual edges,” Ars Math. Contemp., 13, No. 2, 355–366 (2017).Jendrol’ S. and Macekov´a M., “Describing short paths in plane graphs of girth at least 5,” Discrete Math., 338, 149–158 (2015).Jendrol’ S. and Macekov´a M., “Describing short paths in plane graphs of girth at least 5,” Discrete Math., 338, 149–158 (2015).

The authors declare that there are no conflicts of interest present.