Discrete Mathematics 21-228: Summer II 2000
Homework 7
Due Friday, 8/4

You may discuss the problems in groups of at most 3 people, but each person must write her own homework. Please list the members of your group. You may not use any sources other than the notes and texts listed on the course page.

The Lazy Postman

Every morning the lazy postman takes a bus to the post office. Starting there, he arranges his route so that he ends up at home to go back to sleep as quickly as possible (NOT back at the post office). Below is a map of the streets along which he must deliver mail, giving the number of minutes required to walk each block, whether delivering or not. P denotes the post office, and H denotes home. What must the duplicated edges satisfy? What is the optimal route?

A $k$ for 1 sale

We showed in class that every $k$-regular bipartite graph has a perfect matching, for $k \geq 1$. Use this to show that every $k$-regular bipartite graph can be partioned into $k$ perfect matchings.

Extra Credit

Exhibit a perfect matching in the graph below or give a short proof that it has none.

[Hint: Is the graph bipartite?]