4 Let Gbe a simple planar graph containing no triangles i Us

4. Let Gbe a simple planar graph containing no triangles. i) Using Euler\'s formula, show that G contains a vertex of degree at most 3. (ii) Use induction to deduce that G is 4-colourable.

Solution

ii>

a triangle-free planar graph always has a vertex with degree 3 or less. any graph on 4 (or less) vertices is 4-colourable

Lets say , every triangle-free planar graph on n vertices is 4-colourable. Now take any triangle-free planar graph on (n+1) vertices.

If the graph has a vertex with degree three or less then remove it, the remaining graph can be 4 coloured by the induction hypothesis. The removed vertex had 3 or less neighbours only so we can colour it using the fourth colour.

There is always a vertex having degree 3 or less. We can suppose that the graph is connected and has at least 4 vertices.

If it is not connected than take any connected component of the graph. Every face has at least 4 edges. Hence the number of edges is at least 2f. v-e+f=2 implies v-e+e/2 is at least 2. So, on one hand e<=2v-4.

On the other hand the sum of the degrees is 2e. If every vertex had degree 4 or larger then 2e would be at least 4v which is not possible since e<=2v-4.

Hence we could deduce that G is 4 colourable.