Simple planar graph

137 Views Asked by At

What's the best way of proving this?

Let G be a simple planar graph with girth > 3

 1. Prove that G has a vertex of degree at most 3.
 2. Prove that G is 4-colorable
1

There are 1 best solutions below

0
On

$1.$ Assume that $\delta(G)\geq4$. Then $2m\geq 4n$, where $m$ and $n$ denote the size and order of $G$. So $2n\leq m$ and since $G$ contains no triangles we know that $m\leq 2n-4$ which implies that $2n\leq 2n-4$ and so $0\leq -4$ which is a contradiction. Thus $G$ has a vertex of degree at most $3$.

I'm still working on $2.$