Minimal vertex degree sum of a 3-path in plane maps
Oleg Veniaminovich Borodin · Discussiones Mathematicae Graph Theory · 1997
Let w k be the minimum degree sum of a path on k vertices in a graph.We prove for normal plane maps that: (1) if w 2 = 6, then w 3 may be arbitrarily big, (2) if w 2 > 6, then either w 3 ≤ 18 or there is a ≤ 15-vertex adjacent to two 3-vertices, and (3) if w 2 > 7, then w 3 ≤ 17.