Explore BrainMass

# Graphs : Coloring Maps

Not what you're looking for? Search our solutions OR ask your own Custom question.

This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

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.]