SECTION 2.2 Elementary Graph Theory 127
Example 1, continued. We
shall return to the above exam-
ple only long enough to indicate a
minimal-weight spanning tree. In
the next subsection we shall indi-
cate an efficient method to derive
this optimal solution.
Exercises
- Construct (by drawing) a spanning tree in each of the graphs de-
picted below. - Can you give a simple example of a graph which has no Hamilto-
nian cycle? - Indicate a Hamiltonian cycle in the
graph to the right (if one exists).