1.II .17F
Part II, 2006
State and prove Euler's formula relating the number of vertices, edges and faces of a connected plane graph
Deduce that a planar graph of order has size at most . What bound can be given if the planar graph contains no triangles?
Without invoking the four colour theorem, prove that a planar graph that contains no triangles is 4-colourable.