zbMATH — the first resource for mathematics

Solution of Kotzig-Grünbaum problems on separation of a cycle in planar graphs. (Russian) Zbl 0694.05027
Planar pseudographs are considered. The weight w(f) of a face f is the sum of degrees of vertices incident with f. The minimum of weights of faces of a graph G is the weight w(G) of G. The following theorem is proved:
In a planar pseudograph without faces of degree 1 or 2 in which the minimum degree of a vertex is 5 there exists a face of degree 3 whose weight does not exceed 17; this bound cannot be improved.
This theorem is a solution of two problems suggested by A. Kotzig and B. Grünbaum.
Reviewer: B.Zelinka

05C10 Planar graphs; geometric and topological aspects of graph theory
05C38 Paths and cycles