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

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!

• If needed, we may add to $G$ edges making a triangulation. Them it will have $\phi=2n-4$ faces. But my application of Euler formula failed to solve the problem, so I think we need a more subtle approach for this. – Alex Ravsky Nov 7 '17 at 14:41
• Yeah, Euler's formula is not enough – Ivon Nov 7 '17 at 14:53

## 1 Answer

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.