Give a distributed algorithm to 6-color a planar graph.¹ Assume the graph has n vertices and m edges. Your proof should be based on the following two steps.

1. Use Eulers polyhedron formula (which states that if n 3 then m 3n 6) to show that there is always a vertex of degree at most 5.

2. Use the first part above to give the distributed coloring algorithm,

___________________________________________________

¹The celebrated four color theorem states that planar graphs are 4-colorable.