The Art and Craft of Problem Solving

4.1 GRAPH TH EORY 111

the example above), there will be a gap between the end of B2 and the start of AI.
However, £2 must straddle this gap, since it overlaps both B2 and A I. Thus C I , B2, and
£2 overlap (likewise, C 1 , £2, and A I overlap).
This argument involved a 4-cycle (cycle with four vertices), but a little thought
(get out some paper and do some experiments!) shows that it will work with a cycle
of any finite length. We have therefore reduced the problem to a "pure" graph theory
question:

If a graph has 10 vertices and 10 edges, must it contain a cycle?

Connectivity and Cycles

Now that we see how graph theory can completely recast a problem, we shall investi­
gate some simple properties of graphs, in particular the relationship between the num­
ber of vertices and edges and the existence of cycles. The number of edges emanating
from a particular vertex is called the degree of the vertex. If the vertex is x, the degree
is often denoted by d(x). You should easily be able to verify the following important
fact, often called the handshake lemma (if you want a hint, reread Example 3. 4 .7 on
page 95).

In any graph, the sum of the degrees of all th e vertices is equal to twice

th e number of edges.

A graph is connected if every pair of vertices has a path between them. If a
graph is not connected, one can always decompose it into connected components. For
example, the graph below has 10 vertices, 11 edges, and two connected components.
Observe that the handshake lemma does not require connectivity; in this graph the
degrees (scanning from left to right, from top to bottom) are^1 ,2,1, 1,3,3,2, 4 ,3,2.
The sum is 22 = 2. 11.

A connected graph that contains no cycles is called a tree.^2 For example, the
following 8-vertex graph is a tree.

(^2) A non-connected graph containing no cycles is called a forest; each of its connected components is a tree.