11.4 Spanning Trees

Question 1

Spanning Tree

Answer 1

Let G be a simple graph. A spanning tree of G is a subgraph of G that is a tree containing every
vertex of G.

Question 2

Span. Tree Theorem 1

Answer 2

A simple graph is connected if and only if it has a spanning tree.

Question 3

Depth-First Search

Answer 3

A spanning tree can be built by doing a depth-first search of the graph.
• Start with arbitrarily chosen vertex of the graph as the root.
• Form a path from the root by successively adding vertices and edges where
– Each new edge is incident with the last vertex in the path.
– Vertices are not already in the path.
– Continue adding vertices and edges to this path as long as possible,
• If all vertices are included in the path, then “Done”.
• Otherwise, move back to the next to last vertex in the path and, if possible, form a new path
starting at this vertex passing through vertices that were not already visited. If this cannot be
done, move back another vertex and try again.
• Repeat this procedure until no more edges can be added.

Question 4

Depth-First Search

Answer 4

A spanning tree can be built by doing a depth-first search of the graph.
• Start with arbitrarily chosen vertex of the graph as the root.
• Form a path from the root by successively adding vertices and edges where
– Each new edge is incident with the last vertex in the path.
– Vertices are not already in the path.
– Continue adding vertices and edges to this path as long as possible,
• If all vertices are included in the path, then “Done”.
• Otherwise, move back to the next to last vertex in the path and, if possible, form a new path
starting at this vertex passing through vertices that were not already visited. If this cannot be
done, move back another vertex and try again.
• Repeat this procedure until no more edges can be added.

Question 5

Breadth-First Search

Answer 5

• Start with arbitrarily chosen vertex of the graph as the root.
• Add all edges incident to the vertex along with the other vertex connected to each edge
– The new vertices added become the vertices at level 1 in the spanning tree
– Arbitrarily order the new vertices
• For each vertex at level 1, visited in order, add each edge incident to this vertex and the other
vertex connected to the edge to the tree as long as it does not produce a simple circuit
– Arbitrarily order the children of each vertex at level 1
– The new vertices added become the new vertices at level 2 in the spanning tree
• Repeat the procedure until all vertices in the graph have been added

Question 6

Breadth-First Search

Answer 6

• Start with arbitrarily chosen vertex of the graph as the root.
• Add all edges incident to the vertex along with the other vertex connected to each edge
– The new vertices added become the vertices at level 1 in the spanning tree
– Arbitrarily order the new vertices
• For each vertex at level 1, visited in order, add each edge incident to this vertex and the other
vertex connected to the edge to the tree as long as it does not produce a simple circuit
– Arbitrarily order the children of each vertex at level 1
– The new vertices added become the new vertices at level 2 in the spanning tree
• Repeat the procedure until all vertices in the graph have been added