Existence of non-adjacent pair of vertices of small degree in planar graph

Question

Let $G$ be a simple planar graph of order $n\ge5$, and its maximum degree $\Delta=n-1$. Then there exist 2 non-adjacent vertices in $G$ of degree $\le3$ both.

---

I want to use the Euler's formula and prove by contradiction but I cannot get an estimate for $\phi$, the number of faces of the planar graph. Thank you for help!

Answer 1

If we remove from $G$ a vertex of maximum degree then the obtained graph (which from now will be called (new) $G$) will be outerplanar:

An outerplanar graph is an undirected graph that can be drawn in the plane without crossings in such a way that all of the vertices belong to the unbounded face of the drawing. That is, no vertex is totally surrounded by edges. lternatively, a graph $G$ is outerplanar if the graph formed from $G$ by adding a new vertex, with edges connecting it to all the other vertices, is a planar graph.

The vertices $y$ and $z$ of new graph $G$ with at least five vertices obtained in the proof of Theorem 5.20 of “Chromatic Graph Theory” by Gary Chartrand and Ping Zhang should be non-adjacent and both have degree $\le 2$. The respective claim when new $G$ has only four vertices is obvious.