Limiting shape of the Depth First Search tree in an Erdős-Rényi graph

Nathanaël Enriquez, Gabriel Faraud, Laurent Ménard

We show that the profile of the tree constructed by the Depth First Search Algorithm in the giant component of an Erdős-Rényi graph with $N$ vertices and connection probability $c/…