Some graph problems
involve "walking" from one vertex to another by moving along a
sequence of edges, where each edge shares a vertex with the next edge in the
sequence. In formal terms, a walk
from x0 to xn is
a sequence of edges that we denote by a sequence of vertices x0, xl,..., xn such that there is an edge from xi-1 to xi, for 1 ≤ i ≤ n. A walk allows the possibility that some
edge or some vertex occurs more than once. For example, in the graph of Figure 3.6,
the sequence b, c, d, b, a is a walk
that visits b twice and the sequence a, b, c, b, d is a walk that visits b twice and also uses the edge between b and c twice.
A trail
is a walk in which no edge appears more than once. So vertices can be revisited
in a trail, but edges cannot. For example, in the graph of Figure 3.6, the
sequence b, c, d, b, a is a trail that visits b twice but
the sequence a, b, c, b, d is not a
trail.
A path
is a walk in which no edge appears more than once and no vertex appears more
than once, except possibly when the beginning vertex is also the ending vertex.
For example, in the graph of Figure 3.6, the sequence a, b, c, d is a path, but the sequence a, b, c, d, b is not a path because the
vertex b occurs twice. A cycle is a path whose beginning and
ending vertices are equal. The sequence a, b, c, a is a cycle,
but the sequence a, b, a is not a
cycle because the edge from a to b occurs twice.
The length
of a walk (also trail and path) is the number of edges on it. So the length of
the walk x0, xl,..., xn is n. For
example, in the graph of Figure 3.6, the path a, b, d has length two
and the cycle a, b, c, a has length three.

Figure 3.6
Let's emphasize
here that the definitions for walk, trail, path, and cycle apply to both graphs
and directed graphs. But now we come to an idea that needs a separate
definition for each type of graph. A graph is connected if there is a
path between any two vertices. A directed graph is connected if, when direction
is ignored, the resulting undirected graph is connected. A graph with no cycles
is called acyclic. A directed graph that is acyclic is sometimes referred to as
a "DAG" to mean a directed acyclic graph.
Let's look at two
famous graph problems that you may have seen. For the first problem you are to
trace the first diagram in Figure 3.7 without taking your pencil off the paper
and without retracing any line.

Figure 3.7
After some
fiddling, it's easy to see that it can be done by starting at one of the bottom
two corners and finishing at the other bottom corner. The second diagram in
Figure 12.6 emphasizes the graphical nature of the problem. From this point of
view we can say that there is a walk that travels each edge exactly once. In
other words, there is a trail that includes every edge. Since the trail visits
some vertices more than once, our walk is not a path.
The second famous
problem is named after the seven bridges of Kenigsberg
that, in the early 1800s, connected two islands in the river Pregel to the rest of the town. The problem is to find a
trail through the town by walking across each of the seven bridges exactly
once. In Figure 3.8 we've pictured the two islands and seven bridges of Kenigsberg together with a multigraph
representing the situation. The vertices of the multigraph
represent the four land areas and the edges represent the seven bridges.

Figure 3.8
The mathematician Leonhard Euler A707-1783) proved that there aren't any such
trails by finding a general condition for such trails to exist. In his honor, any trail that contains every edge of a graph is
called an Euler trail. For example, the graph for the tracing problem has an
Euler trail, but the seven bridges problem does not. We can go one step further
and define an Euler circuit to be any trail that begins and ends at the same
vertex and contains every edge of the graph. There are no Euler circuits in the
graphs of Figure
3.7 and Figure 3.8.