# Prove that a planar graph with all vertices degree $3$ must has a face with at most $5$ edges.

I have some problems when I prove "For a planar graph $$G$$ and $$\deg(v) = 3$$ for any vertex $$v$$, there is a face with at most $$5$$ edges". I want to prove with contradiction.
Suppose that every face has more than $$5$$ edges.
Then $$2e > 5r$$ ($$e$$ is the number of edges and $$r$$ is the number of faces) because each edge occurs on the boundary of a face exactly twice.
Also, I can get $$2e = 3v$$. (for every edges has $$2$$ vertices)
So we have $$3v > 5r$$.
Then, with Euler's formular: $$r = e - v + 1$$, and $$2e = 3r, 3v > 5r$$ we can get $$r > 20$$.
• Instead of $2e>5r$, you may get more mileage out of $2e\ge6r$. Jun 10, 2020 at 12:25
If $$G = (V, E)$$ is a planar graph with $$|E|\geq g$$ and no cycle of length $$< g$$, then $$e \leq \frac{g}{g − 2}(v − 2)$$. This is a standard generalisation of the result $$e \leq 3v-6$$ which can be proved easily.
In this problem $$g=6$$, so we get $$e \leq \frac{3}{2}(v-2)$$, but since all vertices have degree $$3$$, number of edges is exactly equal to $$\frac{3v}{2}$$, hence a contradiction. Hence the graph must have a face with at most 5 edges.