116 CHAPTER 4 THREE IMPORTANT CROSSOVER TACTICS
This statement is weak, because the hypothesis is so strong. For example, suppose that
G has 50 vertices. Then we need each vertex to have degree at least 25 in order to
conclude that a Hamiltonian path exists.
We urge you to prove 4.1 .6; note that one of the first things you need to do is show
that the hypothesis forces G to be connected.The Two Men of Tibet
Our goal has not been a comprehensive study of graph theory, but merely an introduc
tion to the subject, to give you a new problem-solving tactic and to sensitize you to
think about recasting problems in terms of graphs whenever possible. If you wish to
learn more about this subject, there is a huge literature, but [18], [34], and [43] are all
great places to start (especially [18]).
We will conclude this section with a classic problem that at first does not seem to
have anything to do with graphs.Example 4.1. 7 The Two Men of Ti bet. Two men are located at opposite ends of a
mountain range, at the same elevation. If the mountain range never drops below this
starting elevation, is it possible for the two men to walk along the mountain range and
reach each other's starting place, while always staying at the same elevation?
Here is an example of a "mountain range." Without loss of generality, it is "piece
wise linear," i.e., composed of straight line pieces. The starting positions of the two
men is indicated by two dots.At first, it doesn't seem too hard. As long as it is legal to walk backward, it is pretty
easy for the two men to stay at the same elevation. Let us label the "interesting"
locations on the range (those with elevations equal to the peaks and troughs) with
letters.