Problem Set IV, for Wednesday, October 31
Mathematics 61
Introduction (to Graph Theory)
(page 200 in Discrete Source or page 327 in Discrete Mathematics):
- Exercise 10.
- Exercise 15, and prove by induction on n that
your formula is right.
- Exercise 19. Figure 1.2 is on page 192 or 319.
- Exercise 28, and give the length of your path.
Figure 1.7 is on page 194 or 321.
(The length of a path in a weighted graph is defined on page
195 or 322; it might also be called the weight of the path.)
Note on Exercise 30: My Erdös number is 3.
Paths and Cycles
(page 210 in Discrete Source or page 337 in Discrete Mathematics):
- Exercise 18.
- Exercise 26, and say how many there are.
- Exercise 32.
- Exercises 35 and 36. Support your answer.
There is a supplementary webpage on
Complexity of Decision Problems.
Also here is a map of
old Königsberg.
Compare it with the one on page 205 or 332.
Click here for answers
in .pdf format.