A city consists of five boroughs, and each borough has four neighborhoods and each neighborhood consists of ten houses. You have been hired to run a fiber-optic cable, networking all of the houses to each other. No matter the length, it costs $50 to connect any one house to any other house. Based on all of this information, what will it cost to network all of the houses together so that there are no redundancies? Hint: Think of each house as a vertex.
A) $9950
B) $10500
C) $12500
D) $13500
E) None of the above.

Question

A city consists of five boroughs, and each borough has four neighborhoods and each neighborhood consists of ten houses. You have been hired to run a fiber-optic cable, networking all of the houses to each other. No matter the length, it costs $50 to connect any one house to any other house. Based on all of this information, what will it cost to network all of the houses together so that there are no redundancies? Hint: Think of each house as a vertex. 
A) $9950
B) $10500
C) $12500
D) $13500
E) None of the above.

Quizplus · Accepted Answer

To connect all houses without redundancy, we need a minimum spanning tree. There are 5 boroughs * 4 neighborhoods * 10 houses = 200 houses. A minimum spanning tree for 200 vertices has 199 edges. At $50 per edge, the cost is 199 * $50 = $9950.

A City Consists of Five Boroughs, and Each Borough Has