Question: Assume that arc weights represent distance. Then adding new nodes and arcs to a graph may result in a spanning tree for the new graph that has less weight than a spanning tree for the original graph. (The new spanning tree could represent a minimal-cost network for communications between a group of cities obtained by adding a switch in a location outside any of the cities.)
a. Find a spanning tree of minimum weight for the following labeled graph. What is its weight?
b. Put a node in the center of the square. Add new arcs from the center to the corners. Find a spanning tree for the new graph, and compute its (approximate) weight.