A structural property of planar graphs (Q2713988)

An edge in a plane map is called weak if it is incident with two triangle faces, and semi-weak if it is incident with only one triangle face. The weight of an edge is the sum of the degrees of its vertices. In the article under review, it is proven that every connected plane map with at least two vertices contains either two vertices with the sum of degrees at most 4, or two vertices of degree 3 with distance 2 between them, or a weak edge of weight at most 11, or a semi-weak edge of weight at most 9, or, in addition, an edge of weight at most 7. All the bounds are the best possible as is shown by explicit constructions.NEWLINENEWLINENEWLINEThis result is an enhancement of a similar structural theorem by \textit{V. A. Aksenov, O. V. Borodin, L. S. Mel'nikov, G. Sabidussi, M. Stiebitz}, and \textit{B. Toft} [J. Comb. Theory, Ser. B (to appear)], which was used there to show that from every plane map it is possible to obtain a map with a nontrivial automorphism by removing at most 5 edges.