120 CHAPTER 2 Discrete Mathematics
often abbreviated TSP—and is one of fundamental importance in Man-
agement Science. It is also related to the so-calledP = NPproblem
(one of the Millennium problems)^31 in that a general good (i.e., effi-
cient) solution of TSP would in fact prove that P = NP.
Exercises
- Two of the three graphs below have a Hamiltonian cycle. Deter-
mine which two and in each case find a Hamiltonian cycle. - Find a Hamiltonian cycle of mini-
mal weight in the graph to the right. - Let Gbe a complete graph having six vertices. Suppose that we
label each edge with either a 0 or a 1. Prove that in this graph
there must exist either
(a) three vertices among whose edges are all labeled “0,” or
(b) three vertices among whose edges are all labeled “1.”^32
(^31) See http://www.claymath.org/millinnium.
(^32) This is an elementary example of “Ramsey Theory.” In general, theRamsey numberof a
complete graph withnvertices is the maximum numberksuch an arbitrary labeling of the edges
(with 0s and1s) of the graph will result in a subgraph withkvertices having all the edge labels 0 or