Light subgraphs of multigraphs on compact 2-dimensional manifolds Original Research Article

We have proved that each 3-connected multigraph G without loops and trivial 2-cycles embedded into a compact 2-dimensional manifold M of Euler characteristic χ(M)⩽0 contains a k-path, a path on k vertices, such that each vertex of this path has, in G, degree at most 6k(1−χ(M)/3) for even k⩾2, and at most ⌊(6k−2)(1−χ(M)/3)⌋ for odd k⩾3, or does not contain any k-path. These bounds are shown to be the best possible. Moreover, we have proved that for any graph other than a path no similar bound exists. We also have proved that such multigraphs G of order at least k⩾2 contain subgraphs of order k such that every vertex of these subgraphs has, in G, the degree at most ⌊(4k+4)(1−χ(M)/3)⌋. This bound is also sharp. For large multigraphs of this type the bounds hold with χ(M) replaced by 0; these bounds are again sharp.