Chapter 7, Problem 46E

Figure 7-43(a) shows a network of roads connecting cities $A$ through $G$. The weights of the edges represent the cost (in millions of dollars) of putting underground fiber-optic lines along the roads, and the MST of the network is shown in red. Figure 7-43(b) shows the same network except that one additional road (connecting $E$ and $G$) has been added. Let $x$ be the cost (in millions) of putting fiber-optic lines along this new road.

(connecting E and G) has been added. Let X be the cost (in millions) of putting fiber-optic lines along this new road.

Describe the MST of the network in Figure 7-43(a) in the case $x>59$. Explain your answer.

Describe the MST of the network in Figure 7-43(b) in the case $x<59$. Explain your answer.