Page 3 of 32
• Count 1: Label every half edge by the vertex it ends at. The number of edges labeled with some vertex v is
vdG. So the number of half-edges is
• Count 2: There are clearly twice as many half-edges as edges.
In a graph, the number of vertices with odd degree is even.
GVGV≤even be the set of vertices of G with even degrees. Similarly define
Gvd must be even, so the number of vertices
with odd degree must be even.
1) In a group of 8 persons, is it possible that everyone knows exactly 3 others? Yes.
2) In a group of 7 persons, is it possible that everyone knows exactly 3 others? No.
APPLICATION: THE MOUNTAIN CLIMBERS PUZZLE
Consider 2 mountaineers approaching a mountain range from opposite sides. Is it possible for the climbers to
always be at the same height and reach the summit?
Two mountaineers can indeed clime in the required fashion to the summit of any mountain range.
Construct a graph (the ascent graph) with vertices corresponding to configurations of the climbers where:
1) The two climbers are at the same height.
2) There is one climber on each side of the summit.
3) At least one of the climbers is at a local maxima or minima.
Join the vertices by an edge when the climbers can move between the corresponding configurations by strictly
ascending or strictly descending together.
We must show that no matter for what mountain range, the corresponding ascent graph G has a path from the
ZA, to the summit
We’ll assume no such path exists and produce a contradiction. The proof follows from two observations on G.
Observation 1: G has exactly 2 vertices of degree 1 (namely, the initial configuration and the summit), and the
rest are either degree 2 or 4 (2 when one is on a local max/min, 4 when both are on local max/min at the same
Observation 2: Let
, denote the set of vertices that can be reached by a path from
that the summit
,∉. It is easy to see that there are no edges in G with one end in
V, and one