2.10 Trees

Fill in the blanks!

1. If a graph is _____, then it is guaranteed to have a spanning tree.

   Exercise 1

     simple acyclic 2-colorable connected connected 



2. A _____ of graph \(G \) has all the vertices of \(G \).

   Exercise 2

     exact copy spanning tree spanning subgraph {all of the above} {none of the above} {all of the above} 



3. Any minimum _____ connected spanning _____ is a spanning _____, as proved by the Well-Ordering Principle.

   Exercise 3

     edge, tree, graph weight, tree, graph edge, graph, tree weight, graph, tree edge, graph, tree 



4. We can build a minimum spanning tree using the gray-edges technique, which involves coloring _____ black and white, selecting the _____ gray edge, and reiterating until we obtain a tree.

   Exercise 4

     vertices, minimum-weight components, minimum-weight edges, minimum-length edges, shortest components, minimum-weight 
   CheckShow Answer