DFS on undirected graph gives spanning forest

Dependencies:

1. Spanning forest
2. DFS: White-path theorem

Running DFS on an undirected graph $G$ can be used to find a spanning forest of $G$. This means that every graph has a spanning forest.

Proof

If a root vertex is chosen in a connected component where all vertices are white, then by the white path theorem, all those vertices will become descendants of the root vertex in a rooted tree. This rooted tree will be the spanning tree of that connected component.

Initially all vertices are white, so the first root vertex will be chosen in a connected component where all vertices are white. When processing of that root is complete, all vertices in the first connected component will be black and the rest of the vertices will be white.

Therefore, the next root will again be chosen in a connected component where all vertices are white. When that vertex is processed, the first 2 connected components will be black and the rest will be white. This way, every time a root is chosen, it will be in a connected component where all vertices are white.

(This argument can be made more formal by using induction on the number of connected components processed, but we omit this treatment for now.)

Therefore, when DFS terminates, we will get a spanning forest of the graph.

Dependency for: None

Info:

• Depth: 6
• Number of transitive dependencies: 14

Transitive dependencies:

1. /sets-and-relations/equivalence-classes
2. /sets-and-relations/relation-composition-is-associative
3. /sets-and-relations/equivalence-relation
4. Graph
5. Transpose of a graph
6. Path in Graph
7. Tree
8. Spanning tree
9. Rooted tree
10. Forest
11. Spanning forest
12. Properties of DFS
13. DFS: Parenthesis theorem
14. DFS: White-path theorem