118 CHAPTER 4 THREE IMPORTANT CROSSOVER TACTICS
- If a vertex is of the form (peak, trough), it is isolated (has degree zero). The
vertex (g, q) is an example of this.
Now consider the connected component of r that contains the vertex (a,s). This is a
subgraph of r [it is not all of r, since (g, q) and (q,g) are isolated]. By the handshake
lemma (page 111), the sum of the degrees of the vertices of this subgraph must be
even. Since the only two vertices with odd degree are (a,s) and (s,a) , this subgraph
must contain (s,a) as well. Thus there is a path from (a,s) to (s,a). This argument
will certainly generalize to any mountain range, so we are done. _
s r q p o n m k j h g f e
.. ., .. -1-.. r .. -, .... 1-.. T .. -1-.. � .. ., .. -1-.. r .. -I " .. ,-.. , .. - 1 -.. r" .. ., .. -,.. i" .. -I I I I I I I I I I I I I I I
...... - .. 'i .. -." .. i' .. -... ".- .. i" .. -... ".- .. "'i .. -." ... -.. -.....L .. J .. .. I .... L .. J ....^1 .. L .. _I .... I .... (^1) .. 1 ....... .J .... I
.. .- .. "i I I .... I ,- .. r I .. -, .. "I I I I I I I
.- .. , .. -," .. .- .. 1 .... I
-----------I I I I I I I I -I I ----I I
.. r .. -, .... ,- .. 'T .. -," .. ,. .. ., .... I
.. j" .. -I I I I I I I
." ... - .. i' .. -." .. i" .. "'i ....
L .. J .. .. _I .... L .. .J .. 1 .. L .. I ....^1 .. (^1) .. I .... L .. J .... I
d � .. � .... :- .. T .. -: .... :-.. � .. -: .... � .. � .... :- .. T .. -: .... :-.. � .. -: .... � .. � ....
C r""""" ,-.. r .. -, .... .- .. , .. -," .. r" .. ., .... ,- .. r .. -. .... ,- .. 'T .. -,"" .. ., .... I
b
a I .............................................. I I I I I I I I I - I .......................... I I I I I I -_ .. .. I
abcd e f g h j k m n op qrs
In the end, we solved this hard problem with a very simple parity analysis. Of
course, we first needed the insight of constructing a graph, and the crux move of defin
ing the vertices and edges in a very clever way. The moral of the story: just about
anything can be analyzed with graphs!
Problems and Exercises
In these problems, a graph is not a multigraph (no loops or multiple edges) unless specifically so
stated.
4.1. 8 Show that every graph contains two vertices of
equal degree.
4.1. 9 Given six people, show that either three are mu
tual friends, or three are complete strangers to one an-
other. (Assume that "friendship" is mutual; i.e., if you
are my friend then I must be your friend.)
4.1.10 Seventeen people are at a party. It turns out
that for each pair of people present, exactly one of