Trees are connected, undirected graphs that do not contain cycles.
They are perhaps the simplest interesting class of graphs.
Testing whether a graph is a tree is straightforward using depth-first
search.
During search,
every edge will be labeled either a tree edge or a back edge, so the graph
is a tree if and only if there are no back edges.
Since *m*=*n*-1 for any tree, this algorithm can be said to run in time linear
in the number of vertices.

If the graph is not a tree, it must contain a cycle.
Such a cycle can be identified as soon as the first back edge (*u*,*v*) is
detected.
If (*u*,*v*) is a back edge, then there must be a path in the tree from *v* to
*u*.
Coupled with edge (*u*,*v*), this defines a cycle.

Mon Jun 2 23:33:50 EDT 1997