Massachusetts Institute of Technology Handout ?? 6.042J/18.062J: Mathematics for Computer Science September 26, 2000 Professors Nancy Lynch and Shlomi Dolev

Problem Set 4

Due: 2:35pm in lecture, October 3, 2000.

Be sure to indicate your TA’s name clearly on the solutions your turn in.

—————————————————————————–

Self-study: Matrices Read: Rosen §2.6 Self-study problems (not to be handed in): Rosen §2.6, Exercises 1, 3, 5, 9, 13, 15, 23, 29, 31

—————————————————————————–

Reading: Rosen, Chapters 7 and 8

[[[George: Please type out all problems completely.]]]

Problem 1 At last count, our 6.042 class contains 180 students. Prove that the class must contain either: (a) A set S of 15 students such that, if they line up in size places, they are also arranged in increasing order of age, or (b) A set T of 13 students such that, if they line up in size places, they are also arranged in decreasing order of age.

Problem 2 Rosen 7.4, problem 11 but change the graph in Exercise 2 at least a little (because problem 11 has a solution in the back of Rosen). Type in the new problem. Also, we don’t need 6 parts—maybe just three, the number of paths of length 3, 5, and 7

Problem 3 An Euler path in a digraph G is a path that traverses all the edges of G, each edge exactly once. Unlike an Euler circuit, it need not end up at the same vertex where it started.

Say whether each of the following digraphs has an Euler path, an Euler circuit, both, or neither. Justify your answers by exhibiting the circuits and paths that you say exist, and proving that the others don’t exist.

[[[Put the actual graphs here, without giving them the citation from Rosen.]]]

(a) [[[Digraph from Rosen section 7.5 ex. 24]]]

(b) [[[Digraph from Rosen section 7.5 ex. 26]]]

(c) [[[Digraph from Rosen section 7.5 ex. 28]]] 2 Handout ??: Problem Set 4 Problem 4 For each of the following graphs, (a) find the chromatic number, and (b) say whether it is possible to decrease the chromatic number by removing a single vertex and all edges incident with it. Justify your answers.

(a) The graph in Rosen Section 7.8, exercise 4.

(b) The graph in Rosen Section 7.8, exercise 6.

(c) The graph in Rosen Section 7.8, exercise 8. Problem 5 Prove that in any simple undirected graph, there is a path from any vertex of odd degree to some other vertex of odd degree. Problem 6 Euler or Ham. circuits in undirected graphs Rosen section 7.5, exercise 44. Problem 7 Either draw a full m-ary tree with 76 leaves and height 3 where m is a positive integer, or show that no such tree exists. Problem 8 [[[I’m not yet sure what I’m going to cover on trees. Haven’t finished L07. Possibilities are: Decision trees, which could be covered by Rosen 8.2 exercise 8. Spanning trees, which could be covered by Rosen 8.5 exercise 12 (b).