In a connected network of ‘n’ arcs (roads) joining ‘m’ vertices (towns), a selection of roads is taken up for resurfacing based on a minimum spanning tree of the network as being the least cost solution. This spanning tree will contain.
(a) m arcs (b) (m+1) arcs
(c) (m–1)arcs (d) (m+n–1) arcs