Subgraphs with Restricted Degrees of their Vertices in Large Polyhedral Maps on Compact Two-manifolds

Let k ≥ 2, be an integer and M be a closed two-manifold with Euler characteristic χ(M) ≤ 0. We prove that each polyhedral map G onM , which has at least (8 k2 + 6 k − 6)|χ (M)| vertices, contains a connected subgraph H of order k such that every vertex of this subgraph has, in G, the degree at most 4 k + 4. Moreover, we show that the bound 4k + 4 is best possible. Fabrici and Jendrol’ proved that for the sphere this bound is 10 ifk = 2 and 4 k + 3 if k ≥ 3. We also show that the same holds for the projective plane.