1.II .17F

Graph Theory
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 n3n \geqslant 3 has size at most 3n63 n-6. 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.