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
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
Copyright © 2021 JogjaFile Inc.
$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.$