Discrete Mathematics for Computer Science

Paths and Cycles 341

joined. In some cases, this will not be a subgraph, because vertices are repeated to indicate
that the trail returns to a vertex that has already been included. Figure 6.9 illustrates how
to find a path joining the ends of any trail with repeated occurrences of a vertex.

1 Trail

6 2 2 3 5 4 3 6 1

Repeated Vertex Identified

5 2/ 5 4 3\ 6 1

4 2 3 6 1

Path Formed

Figure 6.9 Refining a trail to find a path.

In addition to trails and paths in a graph we are often interested in trails that have the

same starting and ending vertex.

Definition 6. Let Tr(k) be a trail in a graph G = (V, E) for some k e N. Let the vertices

of Tr(k) be vi, V2 .- Vk. A trail for which v1 = Vk is a circuit. If Tr(k) has its first k - 1

vertices distinct and v, = Vk, then Tr(k) is a cycle. A cycle with three edges is a triangle.

A cycle with k edges where k > 3 is a k-cycle, denoted as Ck. A graph without cycles is

acyclic. A cycle that contains all the vertices of a graph is a Hamiltonian cycle.

Examples of all these notions are found in Figure 6.10.

Circuits

abedcbfa

a bcf beda

f b Cycles

adeba

e c abcdefabcfeb

d Hamiltonian Cycles

abcdefa

adcfeba

Figure 6.10 Circuits and cycles.

6.3.1 Hamiltonian Cycles

A graph that contains a Hamiltonian cycle is called a Hamiltonian graph after William
Hamilton (1788-1856, b. Scotland), who even invented a game based on this notion.
The question of whether a graph is Hamiltonian is not an easy one to answer. A graph
G = (V, E) with as few as I V I edges could be a Hamiltonian graph, but it need not be.
Many of the known sufficient conditions for a graph to be Hamiltonian involve restrictions
on the degrees of the vertices. For example, if every vertex has degree at least I V 1/2, then
the graph must be Hamiltonian. (See Exercises 40 and 41 in Section 6.6.) Showing that a
graph is non-Hamiltonian is often established by observations about conditions Hamilto-
nian graphs must satisfy.