The Art and Craft of Problem Solving

4.1 GRAPH THEORY 113

leaf cannot disconnect it), and has no cycles (since T had no cycles, and plucking a
leaf cannot create a cycle). Hence the new graph is a tree. By the inductive hypothesis,
it must have v - I edges. Thus T has v -I + 1 = v edges. _

4.1.2 Generalize the above by showing that if a collection of disjoint trees (called, of
course, a fo rest) has k connected components, e edges and v vertices, then e = v -k.

4.1. 3 Conclude by showing that

If a graph has e edges and v vertices and e 2 v, then the graph must contain
a cycle.
Note that it does not matter whether the graph is connected or not.
Now we can finish up Example 4.1.1, the problem about the napping mathemati­
cians. The graph in question has 10 edges and 10 vertices. By 4.1 .3, it must contain a
cycle.

Eulerian and Hamiltonian Paths

Problem 2.1 .2 6 on page 24 has a simple graph theory formulation:

Find the conditions on a connected graph (or multigraph) fo r which it

is possible to travel a path that traverses every edge exactly once.^4

Such paths are called Eulerian, in honor of the 18 th-century Swiss mathematician
who first studied graphs in a formal way. Here are two examples that appeared in
Problem 2.1 .26.

A B

Graph A (the vertices are not marked with dots, but are simply the places where the line
segments intersect) has an Eulerian path, while graph B does not. If you draw enough
graphs (and multigraphs), you are inescapably led to focus on the vertices with odd
degree. Let v be a vertex with odd degree in a graph that possesses an Eulerian path.
There are three cases:

1. The path can start at v.


2. The path can end at v.


3. The path starts and ends elsewhere, or is a closed path (no start or end). This
   is not possible, because whenever the path enters v along an edge, it will need
   to exit v along a different edge. This means that d(v) is even.

(^4) More precise language distinguishes between "walks" that avoid repeated edges, called "trails," from walks
that avoid repeated vertices, called "paths." These distinctions are not needed here, but for a very clear discussion,
see Chapter 9 of [15].