algorithm - CLRS Depth First Search Theorem 22.10 -

theorem 22.10 in clrs - introduction algorithms says

in depth first search of undirected graph g, every edge of g either tree edge or edge.

now in explanation tree edge portion obvious, didn't edge part. eg:- take undirected graph such that

1----2----3

now in if edge 1-2 explored first such d1 < d[2], edge 1-2 tree edge. undirected graph can edge 2-1 edge in graph (d[2] > d1) ??

i not getting hang of edge thingy.

i don't have copy of clrs @ hand, i'm writing of head. apologies if stupid.

you edges if have circles.

for given undirected graph can partition set of edges such every edge either tree edge or edge. if original graph happens tree already, set of edges empty. if remove edges graph, graph become tree. naturally there might exist more 1 such partitioning given graph.

in example, graph 1--2--3 tree there no edges. dfs visit each node once. note dfs never uses same edge twice! if used 1-2 go 1 2, cannot go 2-1 via same edge.

the concept of cycle can bit difficult grasp undirected graphs: undirected graph has cycle if can find 2 nodes such can 1 other using more 1 path, not allowed walk same edge twice.