0
$\begingroup$

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$

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So because the graph is 3 regular so 3 regular vertices share 2 edges $\endgroup$ – Fernando Martinez Nov 19 '17 at 22:36
  • $\begingroup$ Each vertex has three edges, this will double count the edges so $2e=3v$. $\endgroup$ – Donald Splutterwit Nov 19 '17 at 22:39

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.