Math 160 Mathematical Problems and Games, Fall 2002
Problem Set 5: hand in one problem Tuesday, October 22.

Instructions:  Think about all four problems, and come up with some ideas about how to solve them. Then choose one of the problems and write up a careful solution. Your solution should be written so that it would convince a skeptical classmate.

1.  Recall the Konigsberg Bridge problem from last time.  In class, we discussed that if one of the bridges (the upper left one in the picture)
 is closed or removed, it is possible to walk around the city going over each bridge once.  

    
a)  Is it possible to do this ending back where you started?  b) Now suppose that the top left bridge is removed, but another bridge is added.  Is it possible to add the new bridge so that you can start anywhere in the city, walk over every bridge exactly once, and end back where you started?

2.  Consider the following graphs, and make up some of your own.  For each graph, a) Is it possible to walk around the graph in such a way that you cover each edge exactly once?  b)  If so, can you start and stop anywhere you like?  
See what patterns you find.  Come up with a rule and try to prove it.



3.  Daydreamer Airlines serves fifteen cities.  From each city, it has direct flights to at least seven other cities.  (And if they fly from A to B, then they also fly from B to A).  Prove that one can fly from any of the fifteen cities to any of the others, possibly taking more than one flight.

4.  In a small village, there are five telephones.  Is it possible to connect them with wires in such a way that each telephone is connected to exactly three others?