After creating a DFS Tree for a graph G, every edge of G is either also an edge in DFS tree or it is a back edge.

The running time of BFS on a graph with vertices and edges represented by an adjacency-matrix is .

In unweighted graph, for any vertex v reachable from s, BFS(s) computes a shortest path from s to v (no path from s to v has fewer edges).

Given an adjacency-matrix representation of the graph, we can compute the degree of a vertex v in O(deg(v)) time, where deg(v) is degree of the vertex v.

In unweighted graph, for any vertex v reachable from s, DFS(s) computes a shortest path from s to v (no path from s to v has fewer edges).