Math 645: A Survey of Mathematical Problems I
Frank Sottile

• The first reading is a discussion of the Traveling Salesman Problem, which in graph theory is of finding the shortest Hamiltonian path/cycle (there are two equally hard versions) in a graph where the edges are given lengths. Equivalently, this is the problem of finding the lowest cost tour, where every edge is given a cost to traverse. It is a particularly easy-to-state example of a large class of important and very hard problems from combinatorial optimization, many of which are outlined in the reading, as well as a discussion of the notion of NP-hard, which is fundamental in complexity theory. This remains important today, as logistics scheduling (course or bus schedules) is a common and very challenging problem that is ubiquitous.
• The reading in selection 13 is a treatise on the four color problem, which was important to the development of graph theory, and whose eventual solution was a landmark in the area. (It was widely reported in the media in the early 1970's enough so that I heard of it then.) I am a big fan of this result, and the much easier five color theorem of Heawood (which is coming to you next week). The approach necessarily used topological properties of planar graphs, which is summarized by Euler's formula.
  It is fun to make the model of Ralph Boas's (Harold's father) Möbius shorts (or in British English Möbius pants).
• As I am back in College Station for the next 4 weeks, I would like to schedule 'office hours' with each of you. If you live in College Station, this will be in my office, and for those of you further away, we can schedule a Skype meeting. I should point out that I can do these any time, working around my schedule. I am in this business because I like working with students and helping them improve themselves.

• Read Selection 12 of the course packet, by Hoffman and Wolfe.
• Read Selections 13, on the four-color problem, and 14, which is fun.
• Chapter 3 of A Survey of Mathematical Problems.
• Dr. Geller's Lecture 6.

1. Exercises 3.8–3.10, and Problems 3.9 and 3.10.
   
2. Problem 3.9 gives a topological proof that there are at most five Platonic solids. Using that in a regular solid, at least three faces (which are regular polygons) meet at each vertex, and for the vertex to be convex, the sum of their angles must be less than 360 degrees, to give the common geometric proof that there are at most five regular solids. Reflect, in a brief paragraph, the value or lack thereof, of different proofs of the same result.