zbMATH — the first resource for mathematics

On vertex-degree restricted subgraphs in polyhedral graphs. (English) Zbl 1007.05063
It is well known that every planar graph contains a vertex of degree at most 5. In 1955 A. Kotzig proved that every 3-connected planar graph contains an edge with degree sum of its vertices being at most 13, the bound being tight. There are several possibilities to generalize and extend the result of Kotzig. The main result of this paper states that every 3-connected planar graph \(G\) of minimum degree at least 4 and order at least \(k\), \(k\geq 4\), contains a connected subgraph \(H\) of order \(k\) such that each vertex of \(H\) has, in \(G\), degree at most \(4k-1\), the bound \(4k-1\) being best possible. This paper brings also a brief survey of some other results generalizing the Kotzig theorem.

05C35 Extremal problems in graph theory
Full Text: DOI