16.5: Spanning Trees
( \newcommand{\kernel}{\mathrm{null}\,}\)
a subgraph that contains all the vertices of the parent graph
a spanning subgraph that is a tree
Here is the complete graph with four vertices.

And here are ten different spanning trees for K4.

If we carry out either of the depth-first or breadth-first search algorithms, but aren't looking for a path between specific vertices, the end result will be a spanning tree for the original graph.
the result of performing the depth-first search algorithm on a graph, continuing until all vertices in the original graph appear in the search tree
the result of performing the breadth-first search algorithm on a graph, continuing until all vertices in the original graph appear in the search tree
Figure 16.5.3 contains depth-first and breadth-first spanning trees for the graph in Figure 16.4.2, our source of examples for depth-first search (Example 16.4.1) and breadth-first search (Example 16.4.2).

