Graphs : Coloring Maps
Not what you're looking for?
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.]
Purchase this Solution
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.
Purchase this Solution
Free BrainMass Quizzes
Geometry - Real Life Application Problems
Understanding of how geometry applies to in real-world contexts
Multiplying Complex Numbers
This is a short quiz to check your understanding of multiplication of complex numbers in rectangular form.
Solving quadratic inequalities
This quiz test you on how well you are familiar with solving quadratic inequalities.
Graphs and Functions
This quiz helps you easily identify a function and test your understanding of ranges, domains , function inverses and transformations.
Know Your Linear Equations
Each question is a choice-summary multiple choice question that will present you with a linear equation and then make 4 statements about that equation. You must determine which of the 4 statements are true (if any) in regards to the equation.