Given a mountain range, as in figure 1, we ask if it is possible for two climbers, Alice and Bob, starting at points A and B, to meet each other by traversing the mountain range in such a way that they maintain the same altitude at all times.
First, we must define what we mean by a mountain range. Informally, we think of a mountain range simply as a series of alternating peaks and valleys. Furthermore, we require that the endpoints of the mountain range are at the same level (say, sea level) and that no valley goes lower than sea level. We can make this definition more formal, but it requires some tedious notation.
Wherever there is a peak or a valley, we draw a horizontal line through it, which extends across the entire range. Label the intersections of these horizontal lines and the mountain range.
The vertices of our graph will be ordered pairs of points, (X, Y), on the same horizontal line such that
There is an edge between two vertices (X1, Y1) and (X2,Y2) if and only if Alice and Bob, starting at locations X1 and Y1 respectively, may move constantly in the same directions (ie: both going up or both going down) to locations X2 and Y2. Notice that since Alice and Bob can travel at arbitrary speed, this condition implies that, as they proceed from (X1, Y1) to (X2, Y2), they may maintain the same altitude.
The graph in figure 3 corresponds to the mountain range in figure 2.
So, what is the relation of this graph to our problem? The starting position corresponds to the vertex (A, B) on our graph. Further, the two climbers will meet if they are at a vertex of the form (X, X). Finally, Alice will meet Bob if and only if there is a path from (A,B) to one of the desired vertices. Thus, we have to show that, given any mountain range, its associated graph has such a path.
Theorem: In any graph G, the sum of the degrees of all the vertices in G is equal to twice the number of edges in G.
Proof: Each edge corresponds to two vertices, one at each end. Hence, by summing the degrees of the vertices, we count each edge twice: once for each endvertex.
Corollary: In any graph, the number of vertices with odd degree is even.
Proof: The sum over all degrees is even, by the above theorem. Thus, the number of odd terms (ie: vertices of odd degree) in the sum is even.
Case 1:
X=A, Y=B.
There is only one choice from the starting postion,
so this vertex has degree one.
Case 2:
X is a peak or a valley, and Y is a peak or a valley, respectively.
Without loss of generality, assume that both X and Y are peaks.
Once Alice is at postion X she can follow the left path or the
right path down. Similarly, Bob has the same choices. Thus,
looking at vertex (X, Y), the edges coming out correspond to
both going to the left, both going to the right, and the two
cases where they head in opposite directions. We conclude that
this vertex must have degree four.
Case 3:
X is peak or a valley, Y is a valley or a peak, respectively.
Clearly, any vertex of this form has degree zero since the
climbers could neither reach nor leave it.
Case 4:
Either X or Y is not a peak or valley.
Without loss of generality,
we can assume Alice is at a peak and Bob has climbed up and
stopped before his peak. Symmetric arguments will hold for all
other cases. Well, Alice has the choice of left or right, but
she must climb downwards. So Bob has no choice. Thus any vertex in
this case will have degree 2.
Case 5:
X=Y.
These configurations correspond precisely to the situations
where Alice and Bob may meet. Assume without loss of generality that they
meet at a peak. From this configuration, Alice and Bob may leave the peak
together or they may split up. If they stay together, we have two
possibilites: they both go left or they both go right. If they split up,
we have only one possibility: Alice goes left and Bob goes right. This fact
arises from our definition of which positions constitute vertices. We
only allow situations where Alice is to the left of Bob. So, vertices
of the form (X, X) have degree 3, unless X=Y=A or X=Y=B in which case
it is clear that (A,A) and (B,B) have degree 1.