1.II .17F
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.
Typos? Please submit corrections to this page on GitHub.