Explore BrainMass

Graphs : Coloring Maps

Let G be a cubic plane graph. Prove that the map M(G) is 3-colourable iff each country has an even number of sides.

note: if we omit the vertices and edges of a plane graph G from the plane, the remainder falls into connected components, called "faces." Clearly each plane graph has exactly one unbounded face. The boundary of a face is the set of edges in its closure. Since a cycle (that is a simple closed polygon) separates the points of the plane into 2 components, each edge of a cycle is in the boundrary of 2 faces. A plane graph together with the set of faces it determines is called a plane map. The faces of a plane map are usually called "countries." 2 countries are neighbouring if their boundaries have an edge in common.

[One direction is not that bad. The other direction can be done by induction on the number of regions or by using the problem 157578 applied to the dual graph and then coloring its vertices.]

Solution Summary

Colored maps are investigated. The solution is detailed and well presented. The response was given a rating of "5/5" by the student who originally posted the question.