In: Advanced Math
Let G be a simple planar graph with no triangles.
(a) Show that G has a vertex of degree at most 3. (The proof was sketched in the lectures, but you must write all the details, and you may not just quote the result.)
(b) Use this to prove, by induction on the number of vertices, that G is 4-colourable.