# Prove that the order of every 3 regular planar graph containing no triangle

Prove that the order of every 3 regular planar graph containing no triangle or 4 cycle is at least 20.

Not sure how to do this problem. I know that because it has no triangle or 4 cycle each region must contain at least 5 edges. And then we have the formula for every connected plane graph of order n, size m and having r regions then

$n-m+r=2$

But I am not sure how to show $n\ge20$

Let $v$ denote the number of verticies, the graph is $3$-regular so $2e=3v$ where $e$ is the number of edges. Every face contains at least $5$ verticies (each vertex will be used in $3$ faces) so $f \geq 3v/5$. Now use Euler's equation $f-e+v=2$ \begin{eqnarray*} v \left( \frac{3}{5}- \frac{3}{2}+1 \right) \geq 2 \end{eqnarray*} and the result follows.
• Each vertex has three edges, this will double count the edges so $2e=3v$. – Donald Splutterwit Nov 19 '17 at 22:39