Discrete Mathematics with Graph Theory (3rd Edition) 368

# Discrete Mathematics with Graph Theory (3rd Edition) 368 -...

This preview shows page 1. Sign up to view the full content.

366 2. (a) [BB] We show the graph superimposed over the given map. Since this graph contains triangles, at least three colors are necessary. A 3-coloring is shown, so the chromatic number is 3. Solutions to Exercises (b) [BB] False! The Four-Color Theorem says that the chromatic number of a planar graph is at most 4. The planar graph in (a) has chromatic number 3. 3. [BB] In neither case, will four colors necessarily suffice as the pictures to the right demonstrate. (a)~ 1 2 5 4 3 (b)~
This is the end of the preview. Sign up to access the rest of the document.

Unformatted text preview: 5 5 3 4 2 4. (a) A 4-coloring is shown; hence, X(Q) ~ 4. Since JC 4 is a subgraph, X(Q) = 4. (b) [BB] A 5-coloring is shown; hence, X(Q) ~ 5. Since JC 5 is a subgraph, X(Q) = 5. (c) A 3-coloring is shown; hence, X(Q) ~ 3. Since JC 3 is a subgraph, X(Q) = 3. (d) A 3-coloring is shown; hence, X(Q) ~ 3. Since Q contains JC3 as a subgraph, X(Q) = 3. (e) [BB] A 4-coloring is shown; hence, X(Q) ~ 4. Since Q contains JC4 as a subgraph, X(Q) = 4. 1 2 1 m 3 4 2 '~ la 2 1 2 1~ at2tV' 2 1 2...
View Full Document

{[ snackBarMessage ]}

Ask a homework question - tutors are online
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}