Note on an existence of small degree vertices with at most one big degree neighbour in planar graphs

Year, pages: 2005, 149 - 153

Let $G$ be a planar graph of minimum degree at least three that does not contain an edge with degree sum of its endvertices at most 8. We prove that every such graph $G$ contains a vertex of degree $d, d in {3,4,5}$, which has at least $d-1$ neighbours each of which has degree at most 20. The bound 20 is tight.

Jendroľ, S., Madaras, T. 2005. Note on an existence of small degree vertices with at most one big degree neighbour in planar graphs. In Tatra Mountains Mathematical Publications, vol. 30, no.1, pp. 149-153. 1210-3195.

Jendroľ, S., Madaras, T. (2005). Note on an existence of small degree vertices with at most one big degree neighbour in planar graphs. Tatra Mountains Mathematical Publications, 30(1), 149-153. 1210-3195.