Subgraphs with restricted degrees of their vertices in large polyhedral maps on compact two-manifolds (Q1970077)

It is shown that for any closed two-manifold \(\mathbf M\) with Euler characteristic \(\xi({\mathbf M})\leq 0\), any integer \(k\geq 1\), and any integer \(N>(8k^2+6k-6) |\xi({\mathbf M})|\) any polyhedral map \(G\) on \(\mathbf M\) with at least \(N\) vertices contains a connected subgraph \(H\) of order \(k\), such that every vertex of \(H\) has in \(G\) degree at most 6 (if \(k=1\)) and at most \(4k+4\) (for \(k\geq 2\)). These bounds are best possible. If, instead of \(\mathbf M\), one considers the projective plane, then these bounds for the vertex degrees are 5 and 10 (for \(k=1\) and \(k=2\) respectively), and \(4k+3\) for any \(k\geq 3\). Similar bounds were previously known for the sphere. The paper contains a good survey that clearly points out the place of the current research in the subject.