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.