Light subgraphs in planar graphs of minimum degree 4 and edge‐degree 9

A graph H is light in a given class of graphs if there is a constant w such that every graph of the class which has a subgraph isomorphic to H also has a subgraph isomorphic to H whose sum of degrees in G is ≤  w . Let $\cal G$ be the class of simple planar graphs of minimum degree ≥ 4 in which no two vertices of degree 4 are adjacent. We denote the minimum such w by w ( H ). It is proved that the cycle C s is light if and only if 3 ≤  s  ≤ 6, where w ( C 3 ) = 21 and w ( C 4 ) ≤ 35. The 4‐cycle with one diagonal is not light in $\cal G$ , but it is light in the subclass ${\cal G}^T$ consisting of all triangulations. The star K 1, s is light if and only if s ≤ 4. In particular, w ( K 1,3 ) = 23. The paths P s are light for 1 ≤  s ≤ 6, and heavy for s  ≥ 8. Moreover, w ( P 3 ) = 17 and w ( P 4 ) = 23. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 261–295, 2003