properties of depth-first search there are number of observations that we can make about the depth-first search algorithmmany of which derive from the way the dfs algorithm partitions the edges of graph into groups we begin with the most significant property proposition let be an undirected graph on which dfs traversal starting at vertex has been performed then the traversal visits all vertices in the connected component of sand the discovery edges form spanning tree of the connected component of justificationsuppose there is at least one vertex in ' connected component not visitedand let be the first unvisited vertex on some path from to (we may have wsince is the first unvisited vertex on this pathit has neighbor that was visited but when we visited uwe must have considered the edge (uv)henceit cannot be correct that is unvisited thereforethere are no unvisited vertices in ' connected component since we only follow discovery edge when we go to an unvisited vertexwe will never form cycle with such edges thereforethe discovery edges form connected subgraph without cycleshence tree moreoverthis is spanning tree becauseas we have just seenthe depth-first search visits each vertex in the connected component of be directed graph depth-first search on starting at proposition let vertex visits all the vertices of that are reachable from alsothe dfs tree contains directed paths from to every vertex reachable from visited by dfs starting at justificationlet vs be the subset of vertices of vertex we want to show that vs contains and every vertex reachable from belongs to vs suppose nowfor the sake of contradictionthat there is vertex reachable from that is not in vs consider directed path from to wand let (uvbe the first edge on such path taking us out of vs that isu is in vs but is not in vs when dfs reaches uit explores all the outgoing edges of uand thus must reach also vertex via edge (uvhencev should be in vs and we have obtained contradiction thereforevs must contain every vertex reachable from we prove the second fact by induction on the steps of the algorithm we claim that each time discovery edge (uvis identifiedthere exists directed path from to in the dfs tree since must have previously been discoveredthere exists path from to uso by appending the edge (uvto that pathwe have directed path from to note that since back edges always connect vertex to previously visited vertex ueach back edge implies cycle in gconsisting of the discovery edges from to plus the back edge (uv