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!

  • $\begingroup$ 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. $\endgroup$ – Alex Ravsky Nov 7 '17 at 14:41
  • $\begingroup$ Yeah, Euler's formula is not enough $\endgroup$ – Ivon Nov 7 '17 at 14:53

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.