Discrete Mathematics: Elementary and Beyond

12.1 A Planet Under Attack 191 1 2 3 4 (^65) FIGURE 12.2. Flooding the island. To flood 6 basins, 6 dams must be blown up. FIGUR ...

192 12. Euler’s Formula FIGURE 12.4. The planar map given bynstraight lines. 12.2 Planar Graphs Which graphs can be drawn as pla ...

12.2 Planar Graphs 193 for two different countries.) The assumption thatK 5 is planar led us to a contradiction, namely, 10> ...

194 12. Euler’s Formula 12.3 Euler’s Formula for Polyhedra................. There is still an apparently irrelevant question to ...

12.3 Euler’s Formula for Polyhedra 195 into one of the faces and blow it up like balloon. The most familiar solids will be blown ...

196 12. Euler’s Formula 12.3.8Does the ”picture frame” polyhedron in Figure 12.6 satisfy Euler’s For- mula? ...

13 Coloring Maps and Graphs 13.1 Coloring Regions with Two Colors We draw some circles on the plane (say,nin number). These divi ...

198 13. Coloring Maps and Graphs FIGURE 13.1. Two-coloring the regions formed by a set of circles. Proof. We prove the assertion ...

13.2 Coloring Graphs with Two Colors 199 the two regions on both sides of the arc were one and the same before we putCback, and ...

200 13. Coloring Maps and Graphs As in Chapter 7, the solution is much easier if we make a drawing of the information we have. W ...

13.2 Coloring Graphs with Two Colors 201 up with two adjacent vertices with the same color. We can generalize this observation t ...

202 13. Coloring Maps and Graphs a u v u 1 u 2 FIGURE 13.5. Bad 2-coloring yields an odd cycle. 13.2.1Prove that the graph obtai ...

13.3 Coloring graphs with many colors 203 All this backtracking takes a lot of time. We don’t give a rigorous analysis here, jus ...

204 13. Coloring Maps and Graphs Unfortunately, for every positive integerkthere are graphs that contain no such complete graph ...

13.4 Map Coloring and the Four Color Theorem 205 FIGURE 13.7. Four mutually neighboring countries boundary, and so all four need ...

206 13. Coloring Maps and Graphs cannot get any of the three colors red, blue, or yellow, so we must use a fourth color (see Fig ...

13.4 Map Coloring and the Four Color Theorem 207 FIGURE 13.9. A graph and its dual Mongolia.) For the purpose of studying colori ...

208 13. Coloring Maps and Graphs because a planar graph can have points of degree higher than 5 (the “dual” graph in Figure 13.9 ...

13.4 Map Coloring and the Four Color Theorem 209 u w uw v FIGURE 13.10. Proof of the 5-color theorem. the same color, so one of ...

210 13. Coloring Maps and Graphs FIGURE 13.11. 2-coloring the regions of a curve 13.4.2LetGbe a connected graph such that all ve ...