Si nous commençons une recherche DFS (profondeur d'abord) sur n'importe quel nœud de S, il est garanti que cette recherche visitera tous les nœuds de S.

Si un nœud v dans S (et ses arêtes incidentes) est retiré de G, il doit toujours exister un chemin reliant n'importe quelle paire de nœuds restants dans S.

Si un appel à la recherche DFS est lancé sur un nœud v dans S, il ne visitera que les nœuds dans S et n'ira pas visiter de nœuds dans une autre composante fortement connexe.