= DFS discovery time
{c}
{title2=$\operatorname{disc}(v)$}
The <DFS discovery time> of a <vertex> is its first-visit number in <depth-first search>, assigned by an increasing counter. Discovery <edges> form a <rooted tree> in each <connected component of a graph>. For the joined-$CD$ example, starting at $A$ and visiting <graph neighbours> in <lexicographic order> gives first visits $A,B,C,D,E,F$, numbered $1,2,3,4,5,6$; its discovery <edges> are $AB,BC,CD,DE,EF$. These numbers encode the chosen traversal, not an invariant of the <graph>.
Back to article page
