Subgraphs with Restricted Degrees of the
β
S. Jendrolβ; H.-J. Voss
π
Article
π
1999
π
Elsevier Science
π
English
β 276 KB
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 on M, which has at least (8k 2 + 6k -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 4k