Discrete Mathematics - Solutions

Solutions to Homework 6 Discrete Mathematics 1. [3.8 #2] We verify that in Figure 3.96(b) there is no K3 and no I5 . Assume that there is a K3 . Call it G0 . By symmetry we can assume that vertex 1 is in G0 . Since the only neighbors of 1 are 2, 6, 9, and 13 then two of these four vertices must be in G0 and thus they must be adjacent. But the graph induced by {2, 6, 9, 13} is an independent graph I4 getting a contradiction. Assume now that there is an I5 , call it G00 . Then there are no consecutive vertices (13 and 1 are considered consecutive, around the polygon) in G00 . By rotational symmetry we can assume that the vertices of G00 are 1, 3, 5, 7, 9, 11. But {1, 9} is an edge and thus G00 6= I5 . 2. [3.8 #5] (a,b) The graph induced by {a, c, e} is a clique of 3 vertices. (c,e) There is no clique or independent set of 3 vertices. (d) The graph induced by {a, b, c} is an independent set of 3 vertices. (f) The graph induced by {a, c, d} is a clique of 3 vertices. 3. [3.8 #10] (a) There are exactly 16 edges incident in a. Each edge gets one of the 3 available colors. By the Pigeonhole Principle at least d16/3e = 6 edges must have the same color. (b) Let G0 be the subgraph induced by {b, c, d, e, f, g}. Then G0 is a K6 whose edges are colored red, blue or white. If one of these edges is red then together with a it forms a red triangle. If none of the edges of G0 is red then G0 is a K6 whose edges are 2-colored (blue or white). Since R(3, 3) = 6, G0 must have a blue or white triangle. 4. [3.8 #11a, d] (a) Consider a coloring of the edges of K3 with 2 colors. By the Pigeonhole Principle at least 2 edges get the same color. Since these two edges must share a vertex, they form a monochromatic L3 . (b) We prove that R (L3 , Z4 ) = 4. In other words, the following two statements are satisfied. First. There is a (red,blue)-coloring of the edge of K3 with no red L3 and no blue Z4 . Color all three edges of K3 blue. Second. Any (red,blue)-coloring of the edges of K4 contains a red L3 or a blue Z4 . Suppose by contradiction that there is such a coloring. This coloring should contain at least one red edge (otherwise we have a blue K4 , which obviously contains a Z4 ). Say uv is a red edge and the other two vertices are x and y. Note that no two red edges are incident (this would form a red L3 ). Thus ux, xv, vy, and yu must be blue. But these for edges form a Z4 (namely, uxvyu) getting a contradiction. 5. [7.1.13] Use Inclusion and Exclusion Principle where a1 , a2 , a3 , and a4 are the properties of being divisible by 2, 3, 5, and 7 respectively. Then the number we are looking for is ¥ ¦ ¥ 600 ¦ ¥ 600 ¦ ¥ 600 ¦ ¥ 600 ¦ ¥ 600 ¦ ¥ 600 ¦ N [a01 , a02 , a03 , a04 ] = 600 − 600 − 3 − 5 − 7 + 6 + 10 + 14 2 ¥ ¦ ¥ 600 ¦ ¥ 600 ¦ ¥ 600 ¦ ¥ 600 ¦ ¥ 600 ¦ ¥ 600 ¦ ¥ 600 ¦ + 600 15 + 21 + 35 − 30 − 42 − 70 − 105 + 210 = 137. 6. [7.1.17] Use Inclusion and Exclusion Principle where a permutation of {1, 2, 3, 4, 5, 6} has property ai if i + 1 immediately follows i, for 1 ≤ i ≤ 5. That is, a permutation has property a1 , a2 , a3 , a4 , or a5 if it has 12, 23, 34, 45, or 56 respectively. For example the permutation 345621 satisfies properties a4 and a5 because 45 and 56 appear. 1 Then the number we are looking for is N [a01 , a02 , a03 , a04 ]. We claim that N [ai ] = 5!, N [ai , aj ] = 4!, N [ai , aj , ak ] = 3!, N [ai , aj , ak , al ] = 2!, N [a1 , a2 , a3 , a4 , a5 ] = 1.and thus µ ¶ µ ¶ µ ¶ µ ¶ µ ¶ £ 0 0 0 0¤ 5 5 5 5 5 5! + 4! − 3! + 2! − 1! = 309. N a1 , a2 , a3 , a4 = 6! − 1 2 3 4 5 Note that N [a1 ], for example, counts the number of permutations of {1, 2, 3, 4, 5, 6} where two immediately follows 1 (having 12). This is the same as the number of permutations of {12, 3, 4, 5, 6} (here 12 is a single element). Similarly to evaluate N [a1 , a2 ] we count the permutations of the 4-element set {123, 4, 5, 6} because any permutation having 12 and 23 actually has 123. The analysis for the pairs [a2 , a3 ] , [a3 , a4 ] , and [a4 , a5 ] is the same. All other pairs behave differently but still give 4!. For example to evaluate N [a1 a3 ] look at the permutations of the 4-element set {12, 34, 5, 6}. N [ai , aj , ak ] is always 3! but we have three different types of triples. To evaluate triples like N [a1 , a2 , a3 ] N [a1 , a2 , a4 ] N [a1 , a3 , a5 ] count permutations of {1234, 5, 6} {123, 45, 6} {12, 34, 56} . Finally To evaluate N [a1 , a2 , a3 , a4 ] N [a1 , a2 , a4 , a5 ] N [a1 , a3 , a4 , a5 ] N [a2 , a3 , a4 , a5 ] count permutations of {12345, 6} {123, 456} {12, 3456} {1, 23456} and the only permutation satisfying all properties is 123456. 7. [7.1.18c, 19c] We compute the chromatic polynomial of K4 in two different ways. First. Using Inclusion and Exclusion Principle. Label the vertices and edges of K4 as in the following picture. 1 a b 2 5 3 d 4 6 c For 1 ≤ i ≤ 6 let ai be the property that in a vertex coloring of K4 the vertices forming edge i get the same color. Then N [ai ] = x½3 , N [ai , aj ] = x2 , x2 if ai , aj , ak form a triangle (4 possibilities) N [ai , aj , ak ] = x otherwise, N [any other set of properties] = x. £ ¤ Then P (K4 , x) = N a01 , a02 , a03 , a04 , a05 , a06 µ ¶ ¶ µ ¶ µ ¶ µµ ¶ 6 6 6 2 6 4 3 2 x+x x− x − 4x − −4 x+ = x − 6x + 5 4 2 3 = x4 − 6x3 + 11x2 − 6x. Second. Using Theorem 7.3. The following are all induced subgraphs of K4 together with their number of edges e and number of components c. 2 e=0 c =4 one e=2 c=2 three e=1 c =3 s ix e=2 c=2 twelve e=3 c=2 four e=3 c=1 twelve e=6 c=1 one e=4 c=1 three e=5 c =1 s ix e=4 c=1 twelve e=3 c=1 four So h (0, 4) = 1, h (1, 3) = 6, h (2, 2) = 15, h (3, 2) = 4, h (3, 1) = 16, h (4, 1) = 15, h (5, 1) = 6, h (6, 1) = 1 and all other h (e, c) = 0. Then by Theorem 7.3 we have X (−1)e h (e, c) xc P (K4 , x) = e,c 4 = x − 6x3 + 15x2 − 4x2 − 16x + 15x − 6x + x = x4 − 6x3 + 11x2 − 6x. 8. [7.2.6(modified)] How many words of length 6 have an even number of different vowels? Solution. Let A be the set of all words of length 6. Then N = |A| = 266 . Consider the following 5 properties on A. a1 = NOT having the letter a, a2 = NOT having the letter e, a3 = NOT having the letter i, a4 = NOT having the letter o, a5 = NOT having the letter u, Then (using the notation in chapter 7) s1 = s2 = s3 = s4 = s5 = µ ¶ 5 ΣN (ai ) = 256 = 5 · 256 , 1 µ ¶ 5 ΣN (ai , aj ) = 246 = 10 · 246 , 2 µ ¶ 5 ΣN (ai , aj , ak ) = 236 = 10 · 236 , 3 µ ¶ 5 226 = 5 · 226 , ΣN (ai , aj , ak , al ) = 4 µ ¶ 5 ΣN (a1 , a2 , a3 , a4 , a5 ) = 216 = 216 . 5 By definition e1 = number of words in A satisfying EXACTLY one property. For example, any word satisfying property a1 but not properties a2 , a3 , a4 , a5 . This means means NOT HAVING the letter a but HAVING the letters e, i, o, u . That is, e1 = # words in A having EXACTLY 4 vowels. 3 Similarly e3 = # words in A having EXACTLY 2 vowels, e5 = # words in A having EXACTLY 0 vowels. Using Theorem 7.5, the number of words in A having an even number of different vowels is ! Ã 5 X 1 e1 + e3 + e5 = (−2)t st s0 − 2 t=0 ¢ 1¡ 6 = 26 − 266 + 2 · 5 · 256 − 4 · 10 · 246 + 8 · 10 · 236 − 16 · 5 · 226 + 32 · 216 2 = 157 140 941. 4